题目：
题解：
解题思路：
复杂度分析：
- 时间复杂度 O(log_2 n) ： 二分的时间复杂度为对数级别。
- 空间复杂度 O(1) ： res, b 等变量占用常数大小额外空间。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20// 超时算法
class Solution {
public double myPow(double x, int n) {
if (n == 0) {
x = 1;
}
if (n < 0) {
x = 1 / x;
n = -n;
}
if (n > 0) {
double a = x;
for(int i = n; i > 1; i--) {
x = x * a;
}
}
return x;
}
}good算法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32// 快速幂法
class Solution2 {
public double myPow(double x, int n) {
if (x == 0) {
return 0;
}
// -n会溢出，但在long形态里面，还是表示的-2147483648，为什么呢？
// n = -2147483648(对应计算机里的补码表示)
// -n 对应计算机里面的真实（补码）表示，和n的补码表示一样，因为已经溢出了，表示不了了。
// 因为根据求相反数的规则：对n求相反数，就对n进行从右往左数，第1个1不变，其他的二进制位变成相反数即可。
// 参考百度百科补码表示：https://baike.baidu.com/item/%E8%A1%A5%E7%A0%81
// int 取值范围 -2^31——2^31-1 -2147483648——2147483647
// b = -n ; // b = -2147483648， 错误代码
// b = -b; // b = 2147483648，正确代码，-b也可以在 正数范围内进行表示。
// 所以必须使用long
long b = n;
double res = 1.0;
if (b < 0) {
x = 1 / x;
b = -b;
}
while (b > 0) {
// （与操作）：判断末尾的二进制数是1还是0
if ((b & 1) == 1) res *= x;
x *= x;
// （移位操作）： nn 右移一位（可理解为删除最后一位）。
b >>= 1;
}
return res;
}
}