Implement pow(x, n).
Solution:O(log n)
public class Solution {
public double pow(double x, int n) {
if(n == 0)
return 1.0;
int flag = 1;
if(x < 0 && (n%2 == 1))
flag = -1;
x = Math.abs(x);
if(x == 1.0)
return x*flag;
if(n<0)
return 1/pow(x, -n);
double ret = 1.0;
double q = x;
while(n>0){
if(n%2 == 1)
ret*=q;
q*=q;
n/=2;
}
return ret*flag;
}
}
Key Concept: Except special case, using previous binary result
沒有留言:
張貼留言