[Leetcode] Sqrt 開方

BlackFlagBin 發布于2019-08-14 12:25 / 3325人閱讀

摘要：二分搜索復雜度時間因為整數長度有限空間思路我們知道必定存在這么兩個整數和，所以我們要做的其實就是縮小這個的范圍。代碼牛頓迭代法復雜度時間空間思路更好的解法是用數學方法，牛頓法是非常經典的求解方程的方法。

Sqrt

Implement int sqrt(int x).
Compute and return the square root of x.

二分搜索 復雜度

時間 O(1) 因為整數長度有限空間 O(1)

思路

我們知道必定存在這么兩個整數a和b,a^2 <= sqrt(x) <= b^2，所以我們要做的其實就是縮小這個ab的范圍。使用二分法解這題時，通過比較mid^2和x大小來確定我們在哪一個半片中搜索。

注意

這題的邊界條件較多，首先high要用long型存儲，其次如果有必要的話要判斷x是否是非負數。

代碼

public class Solution {
    public int mySqrt(int x) {
        long low = 0 , high = x / 2;
        while(low <= high){
            int mid = low + (high - low) / 2;
            if(mid * mid < x){
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return (int)high;
    }
}

牛頓迭代法 復雜度

時間 O(1) 空間 O(1)

思路

更好的解法是用數學方法，牛頓法是非常經典的求解方程的方法。其基本公式是$$ x_{2}=x_{1}-frac{x_{1}^2-n}{2x_{1}} $$，其中x1是上次計算結果，x2是本次計算結果，當他的誤差小于一定值時返回。初始x值可選n/2，或者神奇數0x5f37642f。

代碼

public class Solution {
    public int sqrt(int x) {
        // 如果初始值取0x5f37642f，則會進一步加快計算速度
        double x1 = x/2.0;
        double x2 = 0.0, err = x2 - x1;
        while(Math.abs(err)>0.00000001){
            x2 = x1 - (x1 * x1 - x) / (2 * x1);
            err = x2 - x1;
            x1 = x2;
        }
        return (int)x2;
    }
}

云服務器 GPU云服務器 Sqrt LeetCode linux 開方 python計算開方

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/64460.html

LeetCode69. Sqrt(x) -- 求一個數的開方

摘要：牛頓迭代法的原理很簡單，其實是根據在附近的值和斜率，估計和軸的交點，因此牛頓迭代法的公式為其實就是求切線與軸的交點。代碼利用牛頓法進行的更新，比直接從開始遍歷所作的循環要少牛頓迭代法的基本原理，請參考牛頓迭代法求開平方描述 Implement int sqrt(int x). Compute and return the square root of x, where x is gu...

ddongjian0000 2019-07-30 16:55 評論0 收藏0
[LeetCode] Count Primes

摘要：用數組標記非質數，每當出現一個為，計數器加一。關于質數有三點大于的質數一定是奇數，如，，奇數中的非質數也一定是奇數的乘積。首先，我們用從到進行標記。標記完所有的合數之后，再用到之間的遍歷，所有未被標記的質數。 Problem Count the number of prime numbers less than a non-negative number, n. Note 用數組fla...

Shisui 2019-08-14 15:54 評論0 收藏0
《十萬字Java入門練習100例》1-10例——紙上得來終覺淺,絕知此事要躬行

摘要：代碼實現在控制臺打印總結本篇文章帶大家搭好環境，并體驗了控制臺打印。輸出結果總結熟練掌握取余和整除運算，大有作用。終止本次循環，繼續執行下一次循環。 ?本文收錄...

keithyau 2021-10-09 09:44 評論0 收藏0
Emscripten教程之連接C++和JavaScript（三）

摘要：用具體的參數和返回值調用一個編譯的函數，而是一個編譯的函數的包裹，調用它會返回一個可以調用的函數。如果返回值是或你要指定不同宏，是還是。返回值用于傳給數據。對庫文件的限制調用函數作為中的函數指針使用返回一個整數來表示一個函數指針。翻譯：云荒杯傾本文是Emscripten-WebAssembly專欄系列文章之一，更多文章請查看專欄。也可以去作者的博客閱讀文章。歡迎加入Wasm和emsc...

gyl_coder 2019-08-22 11:10 評論0 收藏0