解題說明
Valid Perfect Square
題目描述:
給定正整數 num,不使用內建的平方根函數,判斷 num 是否為完全平方數。
解題思路:
使用二分搜尋在 [1, num] 範圍內尋找一個整數 mid 使得 mid * mid == num。
- 設定
left = 1,right = num。 - 取中間值
mid,計算mid * mid:- 若等於
num,回傳 true。 - 若小於
num,搜尋右半段left = mid + 1。 - 若大於
num,搜尋左半段right = mid - 1。
- 若等於
- 若搜尋結束仍未找到,回傳 false。
注意使用 long long 避免 mid * mid 溢位。
C++ 解法
複雜度分析
時間複雜度:O(log n) — 標準二分搜尋,每次將搜尋範圍縮小一半。
空間複雜度:O(1) — 只使用常數個變數。
虛擬碼
1. Initialize left = 1, right = num 2. While left <= right: a. mid = left + (right - left) / 2 b. square = mid * mid c. If square == num: return true d. If square < num: left = mid + 1 e. Else: right = mid - 1 3. Return false
其他解法
牛頓迭代法 O(log n):從初始猜測 x = num 開始,反覆更新 x = (x + num / x) / 2 直到 x * x <= num。收斂速度為二次方(每次迭代有效位數加倍),實際上比二分搜尋更快。但需要注意整數除法的向下取整行為。
奇數累加法 O(sqrt(n)):完全平方數等於前 k 個奇數的和:1 + 3 + 5 + ... + (2k-1) = k²。依序減去奇數 1, 3, 5, ...,若 num 減為 0 則為完全平方數。直觀但效率不如二分搜尋。
延伸思考
- 如何用牛頓法求整數平方根?(LeetCode 69)與此題的二分法有何異同?
- 為什麼
mid * mid需要用long long?在什麼範圍的 num 下會發生溢位? - 若要判斷一個數是否為完全 k 次方數(如立方數),如何修改此算法?