50. Pow(x, n)

Medium

Description

實作 pow(x, n)，計算 x 的 n 次方。n 為整數，可能是負數。

Example:

Input: x = 2.0, n = 10 Output: 1024.0

Intuition#

核心思路：快速冪（Binary Exponentiation）——將指數用二進位分解，x^n = x^(n/2) * x^(n/2)，將 O(n) 降到 O(log n)。

暴力法連乘 n 次，時間 O(n)，n 很大時會超時
快速冪利用 x^n = (x^2)^(n/2)（n 為偶數）或 x * (x^2)^((n-1)/2)（n 為奇數）
注意 n 為負數時，先轉換為 1/x 的正數次方；n = Int.MIN_VALUE 時直接取反會溢位

Approaches#

1: 遞迴快速冪#

概念: 遞迴地將問題減半，n 為偶數時 x^n = (x^2)^(n/2)，為奇數時多乘一個 x
時間複雜度: O(log n) - 每次指數減半
空間複雜度: O(log n) - 遞迴深度

class Solution {
    fun myPow(x: Double, n: Int): Double {
        if (n == 0) return 1.0
        if (n < 0) {
            // 處理 Int.MIN_VALUE：先算 x^(-(n+1))，再多除一次 x
            return 1.0 / x * myPow(1.0 / x, -(n + 1))
        }
        return if (n % 2 == 0) {
            myPow(x * x, n / 2)
        } else {
            x * myPow(x * x, n / 2)
        }
    }
}

⭐2: 迭代快速冪#

概念: 將指數看成二進位，從低位到高位，遇到 1 就乘上當前的 x 冪次
時間複雜度: O(log n) - 每次指數減半
空間複雜度: O(1) - 無遞迴

class Solution {
    fun myPow(x: Double, n: Int): Double {
        var base = x
        var exp = n.toLong() // 用 Long 避免 Int.MIN_VALUE 取反溢位
        if (exp < 0) {
            base = 1.0 / base
            exp = -exp
        }
        var result = 1.0
        while (exp > 0) {
            if (exp % 2 == 1L) {
                result *= base
            }
            base *= base
            exp /= 2
        }
        return result
    }
}

n = Int.MIN_VALUE（-2147483648）時，直接取反會溢位，因為 Int.MAX_VALUE = 2147483647。解法是先轉成 Long 再處理。

補充：位元操作版本

用位元操作取代模運算和除法，本質相同但寫法更底層：

class Solution {
    fun myPow(x: Double, n: Int): Double {
        var base = x
        var exp = n.toLong()
        if (exp < 0) {
            base = 1.0 / base
            exp = -exp
        }
        var result = 1.0
        while (exp > 0) {
            if (exp and 1L == 1L) {
                result *= base
            }
            base *= base
            exp = exp shr 1
        }
        return result
    }
}

🔑 Takeaways#

Pattern: 快速冪是「減半」策略的經典應用，時間從 O(n) 降到 O(log n)
關鍵技巧: 注意 Int.MIN_VALUE 的溢位陷阱，養成用 Long 處理邊界的習慣