題⽬描述

給定⼀個⾮負整數 x ，計算並返回 x 的平⽅根，即實現 int sqrt(int x) 函數。

正數的平⽅根有兩個，只輸出其中的正數平⽅根。如果平⽅根不是整數，輸出只保留整數的部分，⼩數部分將被捨去。

示例1
輸⼊：8
返回值：2
解釋：8 的平⽅根是 2.82842…，由於⼩數部分將被捨去，所以返回 2

思路及解答

暴力枚舉

從0開始遞增，找到最大的i滿足i² ≤ x < (i+1)²

public class Solution {
    public int sqrt(int x) {
        // 處理邊界情況
        if (x < 0) return -1; // 輸入非法
        if (x <= 1) return x; // 0和1的平方根是自身
        
        // 從1開始線性查找
        int i = 1;
        while (i <= x / i) { // 使用除法避免溢出
            i++;
        }
        return i - 1; // i是第一個使i² > x的數，所以平方根是i-1
    }
}

• 時間複雜度：O(√x)，最多需要√x次循環
• 空間複雜度：O(1)，只使用常數空間

二分查找（最優解）

在[0, x]範圍內查找平方根，不斷縮小區間，直到找到滿足條件的最大整數

如果 $m^2$ < n, ⽽且 $（m+1）^2$>n，那麼説明 m 是 n 的平⽅根。

public class Solution {
    public int sqrt(int x) {
        if (x < 0) return -1;
        if (x <= 1) return x;
        
        int left = 1;
        int right = x / 2; // 優化：平方根不會超過x/2（x≥4時）
        int result = 0;
        
        while (left <= right) {
            int mid = left + (right - left) / 2; // 防止溢出
            long square = (long) mid * mid; // 使用long防止溢出
            
            if (square == x) {
                return mid; // 找到精確平方根
            } else if (square < x) {
                result = mid; // 記錄當前可能的結果
                left = mid + 1; // 向右查找
            } else {
                right = mid - 1; // 向左查找
            }
        }
        
        return result;
    }
}

• 時間複雜度：O(logn)，每次將搜索範圍減半
• 空間複雜度：O(1)

牛頓迭代法

這就屬於是使用數學方法了

利用切線逼近平方根，迭代公式：xₙ₊₁ = (xₙ + a/xₙ)/2，其中a是要求平方根的數

public class Solution {
    public int sqrt(int x) {
        if (x < 0) return -1;
        if (x == 0) return 0;
        
        double guess = x; // 初始猜測值
        double epsilon = 1e-6; // 精度要求
        
        // 牛頓迭代
        while (Math.abs(guess * guess - x) > epsilon) {
            guess = (guess + x / guess) / 2.0;
        }
        
        return (int) guess; // 向下取整
    }
    
    /**
     * 整數版本：避免浮點數運算
     */
    public int sqrtInt(int x) {
        if (x < 0) return -1;
        if (x <= 1) return x;
        
        long r = x; // 使用long防止溢出
        // 牛頓迭代的整數版本
        while (r * r > x) {
            r = (r + x / r) / 2;
        }
        
        return (int) r;
    }
}

• 時間複雜度：O(log x)，收斂速度極快
• 空間複雜度：O(1)，常數空間

位運算

利用二進制特性逐位確定平方根，最高位開始，逐位嘗試將1變為0或保持1

public class Solution {
    public int sqrt(int x) {
        if (x < 0) return -1;
        if (x <= 1) return x;
        
        int result = 0;
        int bit = 1 << 15; // 從第16位開始嘗試（因為int最大值約21億，平方根約46340）
        
        while (bit > 0) {
            int temp = result | bit; // 嘗試將當前位設為1
            if (temp <= x / temp) { // 等價於temp² ≤ x
                result = temp; // 當前位可以設為1
            }
            bit >>= 1; // 移到下一位
        }
        
        return result;
    }
}

• 時間複雜度：O(log x)，固定32次循環（對於int類型）
• 空間複雜度：O(1)，常數空間

位運算原理解析

為什麼從第16位開始？

• int最大值：2³¹-1 ≈ 21億
• √21億 ≈ 46340 < 2¹⁶ = 65536
• 所以只需要檢查16位即可

執行過程示例（x=8，二進制1000）：

初始: result=0, bit=1<<15=32768
bit太大，跳過...
直到bit=4: temp=4, 4²=16 > 8 → 不設置
bit=2: temp=2, 2²=4 ≤ 8 → result=2
bit=1: temp=3, 3²=9 > 8 → 不設置
返回: result=2