最朴素的想法就是循环,一个一个往上乘,不过这会超时。
需要注意的是指数为负数的情况,只需要把指数取绝对值,最后结果取倒数即可。
方法一:递归快速幂
递归快速幂是从「分治」的角度思考的。
- 计算 $x^n$ 时,先计算 $y = x^{\lfloor n/2 \rfloor }$ ;
- 如果 $n$ 为偶数,则 $x^n = y \cdot y$;如果 $n$ 为奇数,则 $x^n = y \cdot y \cdot x$;
- 递归出口:$x^0 = 1$。
时空复杂度
- 时间复杂度:$O(\log exponent)$
- 空间复杂度:$O(\log exponent)$
Java 代码
class Solution {
public double Power(double base, int exponent) {
if (base == 0) {
return 0;
}
if (exponent < 0) {
return 1.0 / quickPower(base, -exponent);
} else {
return quickPower(base, exponent);
}
}
// 快速幂,注意 long 类型
public double quickPower(double base, long exponent) {
if (exponent == 0) {
return 1.0;
}
double p = quickPower(base, exponent / 2);
if (exponent % 2 == 0) {
return p * p;
} else {
return p * p * base;
}
}
}
方法二:迭代快速幂
迭代快速幂是从「二进制」的角度思考的。
一般地,如果整数 n 的二进制拆分为:
$$
n = 2^{i_{0}} + 2^{i_{1}} + \dots + 2^{i_{k}}
$$
那么:
$$
x^{n} = x^{2^{i_{0}}} \times x^{2^{i_{1}}} \times \dots \times x^{2^{i_{k}}}
$$
详见 Pow(x, n) - LeetCode官方题解。
时空复杂度
- 时间复杂度:$O(\log n)$
- 空间复杂度:$O(1)$
Java 代码
class Solution {
public double Power(double base, int exponent) {
if (base == 0) {
return 0;
}
if (exponent == 0) {
return 1.0;
}
double ans = 1.0;
// Java 中 int 变量 [−2147483648, 2147483647],
// 因此当 n = -2147483648 时执行 n = -n 会因越界而赋值出错。
long N = exponent;
if (N < 0) {
N = -N;
base = 1.0 / base;
}
// 循环计算,当 N == 0 时跳出
while (N > 0) {
// 当 (N & 1) == 1 时,将当前 x 乘入 res
// 如果 N 二进制表示的最低位为 1,那么需要计入贡献
if ((N & 1) == 1) {
ans *= base;
}
// 执行 x = x^2
base *= base;
// 因为已经确保了 N>0,所以不需要使用无符号右移
N >>= 1;
}
return ans;
}
}
膜拜大佬