50 Pow(x, n)

50. Pow(x, n)

1. Question

Implement pow(x,n).
Example 1:
1
Input: 2.00000, 10
2
3
Output: 1024.00000
Copied!
Example 2:
1
Input: 2.10000, 3
2
3
Output: 9.26100
Copied!

2. Implementation

(1) 倍增法
1
class Solution {
2
public double myPow(double x, int n) {
3
if (x == 0) {
4
return 0.0;
5
}
6
7
double res = 1.0;
8
9
while (n != 0) {
10
if ((n & 1) == 1) {
11
if (n > 0) {
12
res *= x;
13
}
14
else {
15
res /= x;
16
}
17
}
18
x *= x;
19
n /= 2;
20
}
21
return res;
22
}
23
}
Copied!

3. Time & Space Complexity

倍增法: 时间复杂度O(logn), 空间复杂度O(1)