LeetCode-Pow(x, n)

Pow(x, n)

##题目

####Pow(x, n)

Implement pow(x, n).

##解题思路
如果对n进行遍历求解，时间复杂度为O(n),这里可以采用二分方法进行优化，是的时间复杂度为O(logn),每次对n进行二分，且只需计算一边即可。

这里需要注意的是：

1. n的正负
2. n的奇，偶性（二分时有影响）

##算法代码
代码采用JAVA实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class Solution {
    public double pow(double x, int n) {
        //对n进行二分，这样时间复杂度为O(logn)
        if(n>=0)
        {
        	return myPow(x,n);
        }else
        	return 1/myPow(x,-n);
    }

    double myPow(double x,int n)
    {
    	if(n==0)
    		return 1;
    	if(n==1)
    		return x;
    	double temp=myPow(x,n/2);
    	if(n%2==0)
    		return temp*temp;   //n为偶数
    	else
    		return temp*temp*x;  //n为奇数
    }
}

Comments

▲