69. Sqrt(x)

解法已隱藏 — 先讀題目敘述、自己想想看，再點上方按鈕揭曉。

69Sqrt(x)Binary SearchEasyBinary Search

給定一個非負整數 x，回傳 x 的算術平方根（取整數部分），即找到最大的整數 r 使得 r * r <= x。

Example:

Input: x = 8 Output: 2（因為 sqrt(8) = 2.828…，取整數部分為 2）

Intuition

TIP

在 [0, x] 上二分搜尋最大的 r 使得 r*r <= x。

本質是找最大的 r 使得 r * r <= x
平方函數具有單調性，適合二分搜尋

Approaches

1. Linear Search — O(sqrt(x)) / O(1)

Idea: 從 0 開始遞增，找到最大的 r 使得 r * r <= x
Time: O(sqrt(x))
Space: O(1)

Linear Search Code

class Solution {
    fun mySqrt(x: Int): Int {
        var r = 0L
        while ((r + 1) * (r + 1) <= x) {
            r++
        }
        return r.toInt()
    }
}

⭐ 2. Binary Search — O(log x) / O(1)

Idea: 在 [0, x] 上二分搜尋，找最大的 mid 使得 mid * mid <= x
Time: O(log x)
Space: O(1)

class Solution {
    fun mySqrt(x: Int): Int {
        var left = 0L
        var right = x.toLong()
        while (left < right) {
            val mid = left + (right - left + 1) / 2
            if (mid * mid <= x) {
                left = mid
            } else {
                right = mid - 1
            }
        }
        return left.toInt()
    }
}

WARNING

找最大可行值的二分模板：left = mid 配合向上取整的 mid（加 1 再除 2），避免死迴圈。

3. Newton's Method — O(log x) / O(1)

Idea: 牛頓法迭代求解 f(r) = r^2 - x = 0，迭代公式 r = (r + x/r) / 2
Time: O(log x)（收斂速度更快）
Space: O(1)

Newton's Method Code

class Solution {
    fun mySqrt(x: Int): Int {
        if (x == 0) return 0
        var r = x.toLong()
        while (r * r > x) {
            r = (r + x / r) / 2
        }
        return r.toInt()
    }
}

🔑 Takeaways

Pattern: 在答案空間上二分搜尋最大可行值
Key trick: 找最大可行值時 mid 要向上取整；牛頓法是更高效的替代方案但面試中二分搜尋更通用

Intuition

Approaches

🔑 Takeaways

相關題目