Sqrt (x) Leetcode шешімі


Күрделілік дәрежесі оңай
Жиі кіреді Amazon алма Bloomberg Google lyft Microsoft қиятын
Екілік іздеу математика

Тақырыпта айтылғандай, санның квадрат түбірін табу керек. Айталық, сан x, онда Sqrt (x) - сан болатындай Sqrt (x) * Sqrt (x) = x. Егер санның квадрат түбірі ондық мән болса, онда біз квадрат түбірдің еден мәнін қайтаруымыз керек.

мысал

4
2
7
2

Тәсіл (алдын-ала жасалған функциялар)

The математика C ++ және. кітапханасы математика 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-ден үлкен әрбір х саны үшін олардың квадрат түбірінің едені х / 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). Қайта, айнымалылар үшін тұрақты кеңістік қолданылады.