[Leedcode][JAVA][第69題][x的平方根][二分查找][數學]

【問題描述】

實作 int sqrt(int x) 函數。

計算并傳回 x 的平方根，其中 x 是非負整數。

由于傳回類型是整數，結果隻保留整數的部分，小數部分将被舍去。


輸入: 8
輸出: 2
說明: 8 的平方根是 2.82842..., 
     由于傳回類型是整數，小數部分将被舍去。


           

【解答思路】

1. 二分法（面試必備）

1.1 縮小邊界 x/2

時間複雜度：O(logN) 空間複雜度：O(1)

Java 代碼要注意到：如果中點 mid 聲明為 int 類型，針對大整型測試用例通不過，是以變量需要聲明為 long 類型。

public class Solution {

    public int mySqrt(int x) {
        // 注意：針對特殊測試用例，例如 2147395599
        // 要把搜尋的範圍設定成長整型
        // 為了照顧到 0 把左邊界設定為 0
        long left = 0;
        // # 為了照顧到 1 把右邊界設定為 x // 2 + 1
        long right = x / 2 + 1;
        while (left < right) {
            // 注意：這裡一定取右中位數，如果取左中位數，代碼會進入死循環
            // long mid = left + (right - left + 1) / 2;
            long mid = (left + right + 1) >>> 1;
            long square = mid * mid;
            //畫圖排除法思想 現象最簡單的 
            if (square > x) {
                right = mid - 1;
            } else {
                left = mid;
            }
        }
        // 因為一定存在，是以無需後處理
        return (int) left;
    }

}



           

1.2 正常思路 零神筆法

時間複雜度：O(logN) 空間複雜度：O(1)

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


           

2.牛頓法

牛頓法得到的是平方根的浮點型精确值（可能會有一定誤差），根據題目中的要求，把最後得到的這個數轉換為 int 型，即去掉小數部分即可

時間複雜度：O(logN) 空間複雜度：O(1)

public class Solution {

    public int mySqrt(int a) {
        long x = a;
        while (x * x > a) {
            x = (x + a / x) / 2;
        }
        return (int) x;
    }
}


           

3. 袖珍電腦算法 零神提供新思路

時間複雜度：O(logN) 空間複雜度：O(1)

class Solution {
    public int mySqrt(int x) {
        if (x == 0) {
            return 0;
        }
        int ans = (int)Math.exp(0.5 * Math.log(x));
        return (long)(ans + 1) * (ans + 1) <= x ? ans + 1 : ans;
    }
}


           

4. 庫函數 皮一下很開心

public int mySqrt(int x) {
        return  (int)Math.sqrt(x);
    }
           

【總結】

1. 一題多解 樂趣多

2.二分法 注意細節

3. 一人之下 真好看

參考連結：https://leetcode-cn.com/problems/sqrtx/solution/x-de-ping-fang-gen-by-leetcode-solution/

參考連結：https://leetcode-cn.com/problems/sqrtx/solution/er-fen-cha-zhao-niu-dun-fa-python-dai-ma-by-liweiw/