[leetcode] Pow(x, n)

[leetcode] Pow(x, n)

題目：

Implement pow(x, n).

分析：
題目很短，就是實現pow求冪函數，直覺告訴我，這個題目的主要要求是降低程序的時間復雜度，果不其然，提交了一份帶有while循環復雜度是O(n)的代碼，返回“Time Limit Exceed“的錯誤，初次提交代碼：

class Solution {
public:
    double myPow(double x, int n) {
        double res = 1;
        while(n > 0)
        {
            res*=x;
            n--;
        }
        return res;

    }
};

然後采用了二進制求冪的思想，對代碼進行了優化，將時間復雜度降低到O(logn)，代碼如下仍然是“Time Limit Exceed“的錯誤。

class Solution {
public:
    double myPow(double x, int n) {
        if(n==0) return 1;
        else
        {
            while((n&1)==0)
            {
                n>>=1;
                x*=x;
            }
        }
        double result=x;
        n>>=1;
        while(n!=0)
        {
            x*=x;
        if((n&1)!=0)
            result*=x;
        n>>=1;
        }
        return result;
    }
};

看來是必須要將復雜性降低到O(1)才能通過了。想著換個思路，能否用到c＋＋標准庫中的東西來做，采用了 x^n = exp(log(x)*n)的算法，降到了O(1)，同時對log函數參數中為負值的情況做了下處理，成功通過，代碼如下：

class Solution {
public:
    double myPow(double x, int n) {
        if(x<0&&n%2==0)
            x = -x;
        if(x<0&&n%2!=0)
          return -exp(log(-x)*n);
        return exp(log(x)*n);
    }
};