LeetCode 50. Pow(x, n)

LeetCode 50. Pow(x, n) 快速幂

题目描述

实现 pow(x, n) ，即计算x的n次幂函数。

示例 1：

输入：x = 2.00000, n = 10 输出：1024.00000

示例 2：

输入：x = 2.10000, n = 3 输出：9.26100

示例 3：

输入：x = 2.00000, n = -2 输出：0.25000 解释：2^(-2) = 1/2^2 = 1/4 = 0.25

提示：

• -100.0 < x < 100.0
• -2^31 <= n <= 2^31-1
• n是一个 32 位有符号整数
• 结果的范围是[-10^4, 10^4]

解题思路

计算x^n最直接的方法是循环相乘，但时间复杂度为 O(n)，当 n 很大时会超时。本题考察的是快速幂算法（又称“二分幂”、“二进制指数运算”），能在 O(log n) 时间内完成计算。

快速幂核心思想

将指数 n 用二进制表示，例如n = 13的二进制为1101，则：

x^13 = x^(8+4+1) = x^8 * x^4 * x^1

我们可以通过不断将底数平方，并检查当前指数二进制的最低位是否为 1，来决定是否乘入结果。具体步骤如下：

1. 初始化结果ans = 1。
2. 当指数n不为 0 时循环：
   • 若当前指数的最低位为 1，则将当前的底数乘入结果。
   • 底数自乘（相当于指数右移一位后，底数变为原来的平方）。
   • 指数右移一位。
3. 循环结束后返回结果。

负指数处理

当指数为负数时，根据公式x^(-n) = 1 / (x^n)，我们可以先取指数的绝对值，并将底数取倒数，然后按正指数计算。

溢出问题

由于n的范围包含-2^31（即 -2147483648），直接取反-n会超出int范围导致溢出。因此，我们先将n转换为long long类型，再进行取反操作。

代码实现（C++）

classSolution{public:doublemyPow(doublex,intn){doubleans=1.0;// 初始化结果longlongm=n;// 使用64位整数，防止 n = INT_MIN 时取反溢出if(m<0){// 处理负指数m=-m;// 指数取绝对值x=1.0/x;// 底数取倒数}while(m){// 快速幂循环if(m&1){// 当前二进制位为1，乘入当前底数ans*=x;}x*=x;// 底数平方，对应指数二进制位的权重m>>=1;// 指数右移一位}returnans;}};

复杂度分析

• 时间复杂度：O(log n)。每次循环指数右移一位，循环次数为指数二进制位数，即 log₂(n)。
• 空间复杂度：O(1)。仅使用了常数个变量。

示例运行

以x = 2.0, n = 10为例：

• m = 10（二进制1010），ans = 1.0。
• 第一轮：m & 1 = 0，不乘；x = 4.0（2²），m = 5（101）。
• 第二轮：m & 1 = 1，ans *= 4.0→ans = 4.0；x = 16.0（4²），m = 2（10）。
• 第三轮：m & 1 = 0，不乘；x = 256.0（16²），m = 1（1）。
• 第四轮：m & 1 = 1，ans *= 256.0→ans = 1024.0；x = 65536.0，m = 0，结束。
• 返回1024.0，正确。

注意事项

1. 必须使用long long存储指数，避免INT_MIN取反溢出。
2. 负指数时先取倒数再计算，结果自然正确。
3. 底数为 0 或指数为 0 时，代码也能正确处理（循环直接跳过，返回初始值 1.0）。

总结

快速幂是处理幂运算的高效算法，其核心在于将指数二进制分解，通过位运算和平方累乘实现 O(log n) 的时间复杂度。本题是快速幂的经典应用，掌握后可用于解决许多类似问题（如矩阵快速幂、斐波那契数列等）。