分析

• 本题的考点：快速幂。

• 关于快速幂的讲解可以参考：快速幂。

• 如果n是正数，可以直接使用快速幂；如果n是负数的话，我们可以对n取绝对值变成正数，然后快速幂，最后结果去个倒数即可。

• 这里需要使用long long，因为当n=-2147483648时取绝对值会溢出，溢出后的值仍然是-2147483648，因此相当于abs(INT_MIN)==INT_MIN。

代码

• C++

class Solution {
public:
    double myPow(double x, int n) {

        typedef long long LL;

        bool is_minus = n < 0;
        double res = 1;
        for (LL k = abs(LL(n)); k; k >>= 1) {
            if (k & 1) res *= x;
            x *= x;
        }
        if (is_minus) res = 1 / res;
        return res;
    }
};

• Java

class Solution {
    public double myPow(double x, int n) {

        boolean is_minus = n < 0;
        double res = 1;
        for (long k = Math.abs((long)n); k > 0; k >>= 1) {
            if ((k & 1) == 1) res *= x;
            x *= x;
        }
        if (is_minus) res = 1 / res;
        return res;
    }
}

时空复杂度分析

• 时间复杂度：$O(log n)$。

• 空间复杂度：$O(1)$。