Medium

题目描述

实现 pow(x, n) ，即计算 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 是一个整数
  • 要么 x 不等于零，要么 n > 0
  • -10^4 <= x^n <= 10^4

解题思路

解题思路

这道题要求实现幂函数，最直接的想法是循环相乘，但当 n 很大时会超时。我们需要使用更高效的算法。

方法一：快速幂（递归）

核心思想是利用 快速幂算法，基于以下数学性质：

  • 如果 n 是偶数：x^n = (x^(n/2))^2
  • 如果 n 是奇数：x^n = x × (x^((n-1)/2))^2

这样可以将时间复杂度从 O(n) 降低到 O(log n)。

方法二：快速幂（迭代）

使用迭代方式实现快速幂，通过位运算判断当前位是否为1，避免递归的额外空间开销。

特殊情况处理

  1. 负指数：如果 n < 0，将问题转换为 1 / x^(-n)
  2. 边界情况：注意 n = -2^31 时取反会溢出，需要特别处理

推荐使用递归方法，代码更简洁易懂，面试时容易快速实现。

代码实现

class Solution {
public:
    double myPow(double x, int n) {
        if (n == 0) return 1.0;
        
        long long longN = n;
        if (longN < 0) {
            x = 1.0 / x;
            longN = -longN;
        }
        
        return fastPow(x, longN);
    }
    
private:
    double fastPow(double x, long long n) {
        if (n == 0) return 1.0;
        
        double half = fastPow(x, n / 2);
        if (n % 2 == 0) {
            return half * half;
        } else {
            return half * half * x;
        }
    }
};

class Solution:
    def myPow(self, x: float, n: int) -> float:
        if n == 0:
            return 1.0
        
        if n < 0:
            x = 1.0 / x
            n = -n
        
        def fastPow(x, n):
            if n == 0:
                return 1.0
            
            half = fastPow(x, n // 2)
            if n % 2 == 0:
                return half * half
            else:
                return half * half * x
        
        return fastPow(x, n)

public class Solution {
    public double MyPow(double x, int n) {
        if (n == 0) return 1.0;
        
        long longN = n;
        if (longN < 0) {
            x = 1.0 / x;
            longN = -longN;
        }
        
        return FastPow(x, longN);
    }
    
    private double FastPow(double x, long n) {
        if (n == 0) return 1.0;
        
        double half = FastPow(x, n / 2);
        if (n % 2 == 0) {
            return half * half;
        } else {
            return half * half * x;
        }
    }
}

/**
 * @param {number} x
 * @param {number} n
 * @return {number}
 */
var myPow = function(x, n) {
    if (n === 0) return 1;
    if (n < 0) {
        x = 1 / x;
        n = -n;
    }
    
    let result = 1;
    while (n > 0) {
        if (n % 2 === 1) {
            result *= x;
        }
        x *= x;
        n = Math.floor(n / 2);
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型快速幂（递归）快速幂（迭代）
时间复杂度O(log n)O(log n)
空间复杂度O(log n)O(1)

相关题目