Sqrt (x) Leetcode Solution  


Რთული ტური Easy
ხშირად ეკითხებიან Amazon Apple Bloomberg Google ლიფტი microsoft Uber
ალგორითმები ორობითი ძებნა კოდირება ინტერვიუ ინტერვიუს მოსამზადებელი LeetCode LeetCodeSolutions მათემატიკის

როგორც სათაური ამბობს, უნდა ვიპოვოთ რიცხვის კვადრატული ფესვი. ვთქვათ, ნომერია x, მაშინ Sqrt (x) ისეთი რიცხვია, რომ Sqrt (x) * Sqrt (x) = x. თუ რიცხვის კვადრატული ფესვი არის ათობითი მნიშვნელობა, მაშინ ჩვენ უნდა დავაბრუნოთ კვადრატული ფესვის იატაკის მნიშვნელობა.

მაგალითი  

4
2
7
2

მიდგომა (წინასწარ ჩამონტაჟებული ფუნქციები)  

ის math C ++ და ენა. მათემატიკა ჯავის ბიბლიოთეკას აქვს წინასწარ ჩაშენებული ფუნქციები რიცხვის კვადრატული ფესვის დასაბრუნებლად. შეგვიძლია მივმართოთ სართული () ნებისმიერი ათობითი მნიშვნელობის თავიდან ასაცილებლად.

ალგორითმი

  1. თუ რიცხვი 2-ზე ნაკლებია, თავად დააბრუნე
  2. დარეკეთ sqrt () ფუნქცია
  3. მიღებული ღირებულების იატაკი
  4. დაბეჭდე შედეგი

Sqrt (x) Leetcode Solution- ის განხორციელება

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';
}

ჯავა პროგრამა

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 x –ზე მეტი, 2 – ზე მეტი, მათი კვადრატული ფესვის იატაკი x / 2.– ზე ნაკლები იქნება. ორობითი ძიების შედეგის მიხედვით, შეგვიძლია გადავიდეთ თავდაპირველი ნიმუშის სივრცის მარცხენა ან მარჯვენა ნახევრებზე.

Sqrt (x)Pin

ალგორითმი

  1. შექმნა binarySearch () sqrt (x) სართულის დაბრუნების ფუნქცია
  2. ცვლადის ინიციალიზაცია წელი შედეგის შესანახად
  3. თუ რიცხვი 2-ზე ნაკლებია, თავად დააბრუნე
  4. ინიციალიზაცია დარჩა და უფლება მნიშვნელობები შესაბამისად 1 და x / 2
  5. მანამდე მარცხნივ <= მარჯვნივ:
    • იპოვნეთ ამ დიაპაზონის შუა რიცხვები, შუა = მარცხნივ + მარჯვნივ / 2
    • იმ შემთხვევაში, თუ შუა კვადრატი ტოლია x,  დააბრუნეთ, რადგან ეს არის კვადრატული ფესვი
    • თუ შუა კვადრატი ნაკლებია x, გადახვიდეთ მარჯვნივ ნახევარში მარცხნივ = ​​შუა რიცხვებით + 1
    • წინააღმდეგ შემთხვევაში, მარცხნივ გადაახვიეთ მარჯვნივ = ​​mid - 1 პარამეტრით და შეინახეთ ეს მნიშვნელობა წელი
  6. დაბეჭდე შედეგი

Sqrt (x) Leetcode Solution- ის განხორციელება

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';
}

ჯავა პროგრამა

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). ისევ და ისევ, მუდმივი სივრცე გამოიყენება ცვლადებისთვის.