Sqrt (x) פתרון Leetcode


רמת קושי קַל
נשאל לעתים קרובות אמזון בעברית תפוח עץ בלומברג Google lyft מיקרוסופט סופר
חיפוש בינארי מתמטיקה

כפי שאומר הכותרת, עלינו למצוא את השורש הריבועי של מספר. נגיד שהמספר הוא x, ואז Sqrt (x) הוא מספר כזה Sqrt (x) * Sqrt (x) = x. אם השורש הריבועי של מספר הוא ערך עשרוני כלשהו, ​​עלינו להחזיר את ערך הרצפה של השורש הריבועי.

דוגמה

4
2
7
2

גישה (פונקציות מובנות מראש)

מתמטיקה ספריית C ++ ו- lang.Math לספריית Java יש את הפונקציות שנבנו מראש להחזרת השורש הריבועי של מספר. אנחנו יכולים להגיש בקשה קוֹמָה() כדי להימנע מכל ערך עשרוני.

אַלגוֹרִיתְם

  1. אם המספר קטן מ- 2, החזיר את עצמו
  2. התקשר sqrt () פונקציה
  3. קבע את הערך שהושג
  4. הדפיס את התוצאה

יישום פתרון Sqrt (x) Leetcode

תוכנית C ++

#include <bits/stdc++.h>
using namespace std;

int mySqrt(int x)
{
    if(x <= 1)
        return x;
    return floor(sqrt(x));
}

int main()
{
    int x = 7;
    cout << mySqrt(x) << '\n';
}

תוכנית Java

import java.lang.Math;

class sqrt_x
{
    static int mySqrt(int x)
    {
        if(x <= 1)
            return x;
        return (int)Math.floor(Math.sqrt(x));
    }

    public static void main(String args[])
    {
        int x = 7;
        System.out.println(mySqrt(x));
    }
}
2

ניתוח מורכבות של אלגוריתם למציאת Sqrt (x)

מורכבות זמן

O (logN). sqrt () הפונקציה משתמשת ב ניוטון-רפסון שיטה לחישוב השורש הריבועי של מספר, אשר מורכבות הזמן שלו היא O (logN).

מורכבות חלל

O (1). מרחב קבוע משמש למשתנים.

גישה (חיפוש בינארי)

כאן נוכל להחיל חיפוש בינארי על טווח מספרים החל מ 1 עולה ל x / 2כאשר x = המספר הנתון. כאן אנו מיישמים את החיפוש הבינארי ברצף ממוין שנבחר במקום ב- מערך.

הגבול הימני מוגדר כ- x / 2 מכיוון שלכל מספר x, גדול מ- 2, רצפת השורש הריבועי שלהם תהיה פחות מ- x / 2. בהתאם לתוצאה של החיפוש הבינארי, נוכל לקפוץ לחצי שמאל או ימין של שטח הדגימה המקורי.

Sqrt (x)

אַלגוֹרִיתְם

  1. צור חיפוש בינארי() פונקצית החזרת קומה של sqrt (x)
  2. אתחל את המשתנה ans לאחסון התוצאה
  3. אם המספר קטן מ- 2, החזיר את עצמו
  4. אתחול עזבו ו תקין ערכים כ- 1 ו- x / 2 בהתאמה
  5. עד שמאל <= ימין:
    • מצא את האמצע בטווח זה, אמצע = שמאל + ימין / 2
    • במקרה שריבוע אמצע שווה ל- x,  להחזיר אותו כמו שהוא השורש הריבועי
    • אם הריבוע של אמצע הוא פחות מ x, קפצו לחצי ימין על ידי הגדרת שמאל = אמצע + 1
    • אחרת, קפצו לחצי השמאלי על ידי הגדרת ימין = אמצע 1 ושמרו ערך זה ב ans
  6. הדפיס את התוצאה

יישום פתרון Sqrt (x) Leetcode

תוכנית C ++

#include <bits/stdc++.h>
using namespace std;

int binarySearch(int x)
{
    int left = 1 , right = x / 2 , mid , ans;
    long temp;

    while(left <= right)
    {
        mid = (left + (right - left) / 2);
        temp = (long)mid * (long)mid;
        //mid * mid can be large, so use long
        if(temp == x)
            return mid;
        if(temp < x)
            ans = mid , left = mid + 1;
        else
            right = mid - 1;
    }
    return ans;
}

int mySqrt(int x)
{
    if(x <= 1)
        return x;
    return binarySearch(x);
}


int main()
{
    int x = 7;
    cout << mySqrt(x) << '\n';
}

תוכנית Java

import java.lang.Math;

class sqrt_x
{
    static int binarySearch(int x)
    {
        int left = 1 , right = x / 2 , mid , ans = 0;
        long temp;

        while(left <= right)
        {
            mid = (left + (right - left) / 2);
            temp = (long)mid * (long)mid;
            //mid * mid can be large, so use long
            if(temp == x)
                return mid;
            if(temp < x)
            {
                ans = mid;
                left = mid + 1;
            }
            else
                right = mid - 1;
        }
        return ans;
    }

    static int mySqrt(int x)
    {
        if(x <= 1)
            return x;
        return binarySearch(x);
    }

    public static void main(String args[])
    {
        int x = 7;
        System.out.println(mySqrt(x));
    }
}
2

ניתוח מורכבות של אלגוריתם למציאת Sqrt (x)

מורכבות זמן

O (logN), כאשר החיפוש הבינארי ממשיך לחלק את שטח הדגימה למחציתו. במקרה הרע, זה יכול לפצות על השוואות logN.

מורכבות חלל

O (1). שוב, נעשה שימוש במרחב קבוע למשתנים.