50. Pow(x, n)

题目链接（中等）

题目描述

实现 pow(x, n)，即计算 x 的整数 n 次幂函数（即 $x^n$）。

数据范围：

-100.0 < x < 100.0
-2^31 <= n <= 2^31 - 1
n 是一个整数
要么 x 不为零，要么 n > 0
-10^4 <= x^n <= 10^4

示例

示例 1：

输入： x = 2.00000, n = 10
输出： 1024.00000

示例 2：

输入： x = 2.10000, n = 3
输出： 9.26100

示例 3：

输入： x = 2.00000, n = -2
输出： 0.25000
解释： $2^{-2} = 1/2^2 = 1/4 = 0.25$

核心思路

朴素做法：直接循环乘 n 次，时间 $O(n)$。

问题：n 最大可达 $2^{31}-1$，$O(n)$ 会超时。

快速幂（分治）：

利用指数运算的性质：

$x^n = \begin{cases} (x^{n/2})^2, & n \text{ 为偶数} \\ (x^{\lfloor n/2 \rfloor})^2 \cdot x, & n \text{ 为奇数} \end{cases}$

每次把指数折半，递归深度为 $O(\log n)$，时间复杂度降为 $O(\log n)$。

负指数处理：

$x^{-n} = \frac{1}{x^n}$

先对 n 取绝对值，算完再取倒数。

方法一：递归快速幂

思路及解法

定义 quickMul(n) 返回 $x^n$：

若 n == 0，返回 1（任何数的 0 次幂为 1）；
递归计算 y = quickMul(n // 2)；
若 n 为偶数，返回 y * y；
若 n 为奇数，返回 y * y * x。

处理负指数：

若 n < 0，返回 1.0 / quickMul(-n)；
否则返回 quickMul(n)。

关于 -n 溢出：在 C++/Java 中，n = -2^31 时 -n 会溢出（int 范围是 $-2^{31}$ 到 $2^{31}-1$）。Python 整数无溢出，可以放心写。如果跨语言实现，需要先把 n 转为 long 再取负。

代码

class Solution:
    def myPow(self, x: float, n: int) -> float:
        def quickMul(n: int) -> float:
            if n == 0:
                return 1.0
            y = quickMul(n // 2)
            if n % 2 == 0:
                return y * y
            else:
                return y * y * x

        if n < 0:
            return 1.0 / quickMul(-n)
        else:
            return quickMul(n)

复杂度分析

时间复杂度：$O(\log n)$，每次递归指数折半。
空间复杂度：$O(\log n)$，递归栈深度。

方法二：迭代快速幂（二进制拆分）

思路及解法

把指数 n 看成二进制，例如 n = 13 = 1101₂，则：

$x^{13} = x^{8} \cdot x^{4} \cdot x^{1}$

迭代过程：

维护 result = 1 和 base = x；
每次看 n 的最低位：
- 若为 1，把 base 乘入 result；
- base 自乘（平方）；
- n 右移一位；
直到 n == 0。

负指数处理：先把 n 转为正数（Python 中直接 n = -n 即可），最后取倒数。

代码

class Solution:
    def myPow(self, x: float, n: int) -> float:
        if n < 0:
            x = 1.0 / x
            n = -n

        result = 1.0
        base = x

        while n > 0:
            if n & 1:
                result *= base
            base *= base
            n >>= 1

        return result

复杂度分析

时间复杂度：$O(\log n)$，循环次数为 n 的二进制位数。
空间复杂度：$O(1)$，只使用常数个变量。

两种方法对比

方法	时间	空间	特点
递归快速幂	$O(\log n)$	$O(\log n)$	代码直观，与分治思想对应
迭代快速幂	$O(\log n)$	$O(1)$	空间最优，面试推荐

关键细节

1. 为什么快速幂是 $O(\log n)$

每次递归（或迭代）指数减半，最多 $\log_2 n$ 层。例如 $n = 2^{31}$ 时也只需 31 层。

2. 负指数的处理

$x^{-n} = \frac{1}{x^n}$

递归法：1.0 / quickMul(-n)；
迭代法：先把 x 取倒数，n 取正，再按正指数计算。

3. `n = -2^31` 的溢出问题

Python：整数无溢出，-n 安全；
C++ / Java：int 范围是 $[-2^{31}, 2^{31}-1]$，-(-2^31) 会溢出。需要先把 n 转为 long 再取负。

4. 迭代法的二进制拆分

以 x^13 为例，13 = 1101₂：

步骤	`n`	`n & 1`	`result`	`base`
初始	13	—	1	$x$
1	13	1	$x$	$x^2$
2	6	0	$x$	$x^4$
3	3	1	$x^5$	$x^8$
4	1	1	$x^{13}$	$x^{16}$
5	0	—	$x^{13}$	—

最终结果 $x^{13}$，正确。

5. 边界情况

n = 0：返回 1.0；
x = 1：任何次幂都是 1；
x = -1：根据 n 的奇偶性返回 1 或 -1；
n = 1：返回 x。

6. 精度问题

题目保证 $|x^n| \le 10^4$，不会出现浮点溢出或下溢。浮点乘法有微小误差，但题目按相对误差判定，通常直接返回即可。

总结

核心思想：快速幂，每次指数折半，时间 $O(\log n)$；
递归法：
- quickMul(n) = quickMul(n//2)^2（偶数）或再乘 x（奇数）；
- 负指数取倒数；
- 空间 $O(\log n)$；
迭代法（推荐）：
- 把 n 看成二进制，逐位判断是否乘入 result；
- base 不断自乘；
- 空间 $O(1)$；
负指数：先取倒数再算正指数；
注意溢出：C++/Java 中 -n 在 n = -2^31 时溢出，需转 long；
通用套路：「求幂」→ 快速幂，指数折半或二进制拆分。

50. Pow(x, n)

50. Pow(x, n)

题目描述

示例

核心思路

方法一：递归快速幂

思路及解法

代码

复杂度分析

方法二：迭代快速幂（二进制拆分）

思路及解法

代码

复杂度分析

两种方法对比

关键细节

1. 为什么快速幂是 $O(\log n)$

2. 负指数的处理

3. n = -2^31 的溢出问题

4. 迭代法的二进制拆分

5. 边界情况

6. 精度问题

总结

相关题目

3. `n = -2^31` 的溢出问题