【LeetCode】50、Pow(x, n)

50、Pow(x, n)

题目：

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

示例1：

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

示例2：

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

示例3：

输入：x = 2.00000, n = -2
输出：0.25000
解释：2-2 = 1/22 = 1/4 = 0.25
1
2
3

提示：

-100.0 < x < 100.0
-2^31 <= n <= 2^31-1
-10^4 <= xn <= 10^4

解题思路：

此题目求 x^n 次方 ，利用数学方法就是

通过循环将 n 个 x 乘起来，依次求 x^1, x^2, ..., x^{n-1}, x^n ，时间复杂度为 O(n) 。

快速幂法：

但是也有一种快速的解法：快速幂法 可将时间复杂度降低至 O(logn)

算法流程：

1. 当 x = 0.0 时：直接返回 0.0 ，以避免后续 1 除以 0 操作报错。分析： 数字 0 的正数次幂恒为
   0 ； 0 的 0 次幂和负数次幂没有意义，因此直接返回 0.0 即可。
2. 初始化 res=1 。
3. 当 n<0 时：把问题转化至n≥0 的范围内，即执行x=1/x ，n=−n 。
4. 循环计算：当 n=0 时跳出。
5. 当 n&1=1 时：将当前 x 乘入 res （即res∗=x ）。
6. 执行 x = x^2（即x∗=x ）。
7. 执行 n 右移一位（即 n>>=1）。
8. 返回 res

复杂度分析：

时间复杂度 O(logn) ： 二分的时间复杂度为对数级别。
空间复杂度 O(1) ： res, b 等变量占用常数大小额外空间。

参考代码：

Java 代码中 int32 变量 n∈[−2147483648,2147483647] ，因此当 n=−2147483648 时执行 n=−n 会因越界而赋值出错。解决方法是先将 n 存入 long 变量 b ，后面用 b 操作即可。

class Solution {
    public double myPow(double x, int n) {
        if(x == 0.0f) return 0.0d;
        long b = n;
        double res = 1.0;
        if(b < 0) {
            x = 1 / x;
            b = -b;
        }
        while(b > 0) {
            if((b & 1) == 1) res *= x;
            x *= x;
            b >>= 1;
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17