Implement pow(x, n).
You don‘t need to care about the precision of your answer, it‘s acceptable if the expected answer and your answer ‘s difference is smaller than 1e-3.
O(logn) time
一开始，直接做的，复杂度O（n）
public class Solution { /** * @param x the base number * @param n the power number * @return the result */ public double myPow(double x, int n) { // Write your code here double res=1; if(n==0) return res; if(n<0) { int digit=Math.abs(n); for(int i=1;i<=digit;i++) { res=x*res; } res=1/res; } else{ for(int i=1;i<=n;i++) { res=x*res; } } return res; } }
复杂度O(logN)
public class Solution { /** * @param x the base number * @param n the power number * @return the result */ public double myPow(double x, int n) { // Write your code here double res=1; if(n==0) return 1; if(n<0) { n=-n; x=1/x; } while(n>0) { if(n%2==1) { res*=x; } n=n/2; x=x*x; } return res; } }
原文：http://www.cnblogs.com/kittyamin/p/5104296.html