Sqrt (x) Leetcode шийдэл


Хэцүү байдлын түвшин Easy
Байнга асуудаг Амазоны Apple-ийн Bloomberg Google-ийн lyft Microsoft- Uber
Хоёртын хайлт Математик

Гарчгийн хэлсэнчлэн бид тооны квадрат язгуурыг олох хэрэгтэй. Энэ тоо гэж хэлье x, Дараа нь Sqrt (x) нь ийм тоо байна Sqrt (x) * Sqrt (x) = x. Хэрэв тооны квадрат язгуур нь аравтын бутархай бол бид квадрат язрын давхар утгыг буцааж өгөх ёстой.

Жишээ нь

4
2
7
2

Хандалт (Урьдчилан бүтээсэн функцууд)

The математик C ++ ба номын сангийн lang Математик 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). The sqrt () функцийг ашигладаг Ньютон-Рафсон O (logN) хугацааны нарийн төвөгтэй тооны квадрат язгуурыг тооцоолох арга.

Сансрын нарийн төвөгтэй байдал

O (1). Тогтмол орон зайг хувьсагчуудад ашигладаг.

Хандалт (Хоёртын хайлт)

Эндээс эхлэн хэд хэдэн тооны тоон дээр хоёртын хайлт хийх боломжтой 1 хүртэл явах х / 2энд x = өгөгдсөн тоо. Энд бид хоёртын хайлтыг an-ийн оронд сонгосон эрэмбэлэгдсэн дарааллаар хэрэгжүүлнэ массив.

Баруун хязгаарыг дараах байдлаар тохируулсан болно х / 2 2-оос их x тоо бүрийн хувьд тэдгээрийн квадрат язгуурын шал x / 2-оос бага байх болно. Хоёртын хайлтын үр дүнгээс хамааран бид анхны түүврийн зайны зүүн буюу баруун тал руу үсрэх боломжтой.

Sqrt (x)

Алгоритм

  1. Бүтээх binarySearch () 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). Дахин хэлэхэд хувьсагчдын хувьд тогтмол орон зайг ашигладаг.