給定一個正整數
num，判斷它是否為完全平方數。不能使用內建的平方根函式。
Example:
Input: num = 16 Output: true
Intuition
TIP
在 [1, num] 上二分搜尋，找是否存在一個整數 x 使得 x*x == num。
- 如果存在整數 x 使得
x * x == num，則 num 是完全平方數 - 在 [1, num] 區間上二分搜尋這個 x
Approaches
1. Try Each — O(sqrt(n)) / O(1)
- Idea: 從 1 開始逐一檢查
i * i == num - Time:
O(sqrt(n)) - Space:
O(1)
Try-Each Code
class Solution {
fun isPerfectSquare(num: Int): Boolean {
var i = 1L
while (i * i < num) {
i++
}
return i * i == num.toLong()
}
}⭐ 2. Binary Search — O(log n) / O(1)
- Idea: 在 [1, num] 上二分搜尋，檢查
mid * mid與num的關係 - Time:
O(log n) - Space:
O(1)
class Solution {
fun isPerfectSquare(num: Int): Boolean {
var left = 1L
var right = num.toLong()
while (left <= right) {
val mid = left + (right - left) / 2
val sq = mid * mid
when {
sq == num.toLong() -> return true
sq < num -> left = mid + 1
else -> right = mid - 1
}
}
return false
}
}WARNING
使用 Long 避免 mid * mid 溢位，num 最大可達 2^31 - 1。
🔑 Takeaways
- Pattern: 二分搜尋判斷存在性
- Key trick: 與 Sqrt(x) (#69) 類似但目的不同：這題是判斷是否存在完美平方根，而非求近似值。注意整數溢位問題