(每日一道算法题)实现 pow(x, n) 的快速幂解法

50. Pow(x, n) - 力扣（LeetCode）

问题描述

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

示例 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/22 = 1/4 = 0.25

提示：

• -100.0 < x < 100.0
• -231 <= n <= 231-1
• n 是一个整数
• 要么 x 不为零，要么 n > 0 。
• -104 <= xn <= 104

关键思路

1. ​​处理负数指数​​：当 n 为负数时，计算结果相当于正数次幂的倒数，即 x^(-n) = 1/(x^n)。
2. ​​避免溢出​​：当 n 是 Integer.MIN_VALUE 时，取负数会导致溢出，因此需要转换为更大的数据类型（如 long）。
3. ​​快速幂算法（分治）​​：利用分治思想，将 x^n 分解为更小的子问题，递归计算：
   • 若 n 为偶数，x^n = (x^(n/2))^2。
   • 若 n 为奇数，x^n = (x^(n/2))^2 * x。

代码实现

class Solution {public double myPow(double x, int n) {long N = n; // 转换为long类型避免溢出return N < 0 ? 1.0 / MyPow(x, -N) : MyPow(x, N);}private double MyPow(double x, long n) {if (n == 0) {return 1.0; // 递归终止条件}double half = MyPow(x, n / 2); // 递归计算子问题return n % 2 == 0 ? half * half : half * half * x; // 合并结果}
}

代码解析

• ​​处理负数指数​​：在主函数中，若 n 为负数，则计算其绝对值的次幂后取倒数。
• ​​避免溢出​​：使用 long 类型存储 n 的绝对值，确保在计算过程中不会溢出。
• ​​快速幂算法​​：递归分解次幂计算，每次将问题规模减半，时间复杂度为 O(log n)，空间复杂度为 O(log n)（递归栈）。

复杂度分析

• ​​时间复杂度​​：O(log n)，每次递归将指数规模减半。
• ​​空间复杂度​​：O(log n)，递归调用栈的深度为 log n。

此方法高效地处理了所有可能的输入情况，包括大数运算和负数指数，确保了正确性和高效性。