Sqrt (x) Ҳалли Leetcode


Сатҳи душворӣ осон
Аксар вақт пурсида мешавад Amazon себ Блумберг Google лимф Microsoft Uber
Ҷустуҷӯи бинарӣ Матем

Тавре ки дар сарлавҳа гуфта мешавад, мо бояд решаи квадратии ададро ёбем. Бигзор шумораи ин аст x, пас Sqrt (x) адад аст, ки Sqrt (x) * Sqrt (x) = x. Агар решаи квадратии адад ягон арзиши даҳӣ бошад, пас мо бояд арзиши қабати решаи квадратиро баргардонем.

мисол

4
2
7
2

Равиш (Функсияҳои қаблан сохташуда)

Дар математика китобхонаи C ++ ва математика Китобхонаи Java дорои функсияҳои қаблан сохташуда барои баргардондани решаи квадратии рақам мебошад. Мо метавонем муроҷиат кунем фарш () барои пешгирӣ кардани ягон арзиши даҳӣ.

Алгоритм

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

Барномаи 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)

Мураккабии вақт

О (logN). Дар sqrt () функсия аз Нютон-Рафсон усули ҳисоб кардани решаи квадратии рақам, ки мураккабии вақти O (logN) дорад.

Мураккабии фазо

О (1). Фазои доимӣ барои тағирёбандаҳо истифода мешавад.

Равиш (Ҷустуҷӯи дуӣ)

Дар ин ҷо, мо метавонем ҷустуҷӯи бинариро дар доираи рақамҳо сар карда, татбиқ кунем 1 ба боло рафтан х / 2ки дар он х = адади додашуда. Дар ин ҷо, мо ҷустуҷӯи бинариро ба ҷои пайдарҳамии интихобшуда амалӣ мекунем асал.

Маҳдудияти рост ҳамчун муқаррар карда шудааст х / 2 зеро барои ҳар як адади х, аз 2 калонтар, қабати решаи квадратии онҳо камтар аз х / 2 хоҳад буд. Вобаста аз натиҷаи ҷустуҷӯи дуӣ, мо метавонем ба нисфҳои чап ё рости фазои намунаи аслӣ ҷаҳем.

Sqrt (x)

Алгоритм

  1. Сохтани а binarySearch () Функсияи бозгашти ошёнаи sqrt (x)
  2. Тағирёбандаро оғоз кунед ҷалбкунанда барои нигоҳ доштани натиҷа
  3. Агар шумора камтар аз 2 бошад, худашро баргардонед
  4. Ибтидоӣ чап ва рост арзишҳо мутаносибан 1 ва x / 2
  5. то чап <= рост:
    • Миёнаи ин диапазонро ёбед, миёна = чап + рост / 2
    • Дар ҳолат, ки мураббаъ аз миёна ба x,  онро ҳамчун решаи квадратӣ баргардонед
    • Агар мураббаъ миёна аз x, бо гузоштани чап = миёна + 1 ба нимаи рост ҷаҳед
    • Дар акси ҳол, бо гузоштани right = 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';
}

Барномаи 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.

Мураккабии фазо

О (1). Боз барои тағирёбандаҳо фазои доимӣ истифода мешавад.