367. Valid Perfect Square

Easy

Description

給定一個正整數 num，判斷它是否為完全平方數。不能使用內建的平方根函式。

Example:

Input: num = 16 Output: true

Intuition#

在 [1, num] 上二分搜尋，找是否存在一個整數 x 使得 x*x == num。

如果存在整數 x 使得 x * x == num，則 num 是完全平方數
在 [1, num] 區間上二分搜尋這個 x

Approaches#

1: 逐一嘗試#

概念: 從 1 開始逐一檢查 i * i == num
時間複雜度: O(sqrt(n))
空間複雜度: O(1)

逐一嘗試程式碼

class Solution {
    fun isPerfectSquare(num: Int): Boolean {
        var i = 1L
        while (i * i < num) {
            i++
        }
        return i * i == num.toLong()
    }
}

⭐2: Binary Search#

概念: 在 [1, num] 上二分搜尋，檢查 mid * mid 與 num 的關係
時間複雜度: O(log n)
空間複雜度: 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
    }
}

使用 Long 避免 mid * mid 溢位，num 最大可達 2^31 - 1。

🔑 Takeaways#

Pattern: 二分搜尋判斷存在性
關鍵技巧: 與 Sqrt(x) (#69) 類似但目的不同：這題是判斷是否存在完美平方根，而非求近似值。注意整數溢位問題