题解 | #数值的整数次方#

思路

最简单的办法就是暴力求解，不停的进行乘法运算。但是这样做很容易就超时了，其时间复杂度是O(n)。

求解这种问题最好的办法就是快速幂。

下面是代码实现。

Java版本

public class Solution {
    public double Power(double base, int exponent) {
        double res = 1.0;
        if (exponent < 0) {
            base = 1 / base;
            exponent = 0 - exponent;
        }

        while (exponent != 0)
        {
            if ((exponent&1) != 0) 
            {
                res *= base;
            }
            base *= base;
            exponent >>= 1;
        }
        return res;
  }
}

c++版本

class Solution {
public:
    double Power(double base, int exponent) {
        if (exponent < 0)
        {
            base = 1 / base;
            exponent = 0 - exponent;
        }
        double ans = 1.0;
        double x = base;
        while (exponent)
        {
            if (exponent & 1 != 0)
            {
                ans *= x;
            }
            x *= x;
            exponent >>= 1;
        }
        return ans;
    }
};

速度都很不错，Java版本用时47ms，C++版本用时4ms。

快速幂算法的时间复杂度只有O(logN)。