剑指 Offer（第2版）面试题 16：数值的整数次方

题目来源：27. 数值的整数次方

不得使用库函数，同时不需要考虑大数问题。

只要输出结果与答案的绝对误差不超过 10⁻² 即视为正确。

注意：

• 不会出现底数和指数同为 0 的情况
• 当底数为0时，指数一定为正
• 底数的绝对值不超过 10，指数的绝对值不超过 10⁹。

解法1：快速幂 - 递归写法

最朴素的想法就是循环，一个一个往上乘，不过这会超时。

需要注意的是指数为负数的情况，只需要把指数取绝对值，最后结果取倒数即可。

注意指数 exponent 要转换成 unsigned int 或者 long long，有一个数据是 10, −2147483648，int 的范围是 −2147483648 ~ 2147483647，对 −2147483648 取绝对值会爆掉，转成 signed int 也会爆。

算法：

代码：

class Solution
{
public:
    double Power(double base, int exponent)
    {
        if (base == 0)
            return 0.0;
        if (exponent >= 0)
            return quickMul(base, (long long)exponent);
        else
            return quickMul(1.0 / base, abs((long long)exponent));
    }
    // 辅函数 - 快速幂
    double quickMul(double base, long long exponent)
    {
        if (exponent == 0)
            return 1.0;
        double y = quickMul(base, exponent / 2);
        if (exponent % 2 == 1)
            return y * y * base;
        else
            return y * y;
    }
};

复杂度分析：

时间复杂度：O(log(exponent))。

空间复杂度：O(log(exponent))。

解法2：快速幂 - 非递归写法

详见 Pow(x, n) - LeetCode官方题解。

代码：

class Solution
{
public:
    double Power(double base, int exponent)
    {
        unsigned int n = abs(exponent);
        double res = 1.0;
        while (n)
        {
            if (n & 01)
                res *= base;
            base *= base;
            n >>= 1;
        }
        if (exponent < 0)
            res = 1.0 / res;
        return res;
    }
};

复杂度分析：

时间复杂度：O(log(exponent))。

空间复杂度：O(1)。