【剑指Offer刷题系列】数值的整数次方

目录

• 问题描述
• 示例
• • 示例 1：
  • 示例 2：
  • 示例 3：
• 思路解析
• • 核心思路：
  • 具体步骤：
  • 复杂度分析：
• 代码实现
• • Python 实现
• 测试代码
• 复杂度分析
• • 时间复杂度
  • 空间复杂度
• 结论

问题描述

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

注意：

• x 是一个双精度浮点数。
• n 是一个整数，可以是正数、负数或零。
• 结果需要保证在 [-10^4, 10^4] 范围内。

提示：

• -100.0 < x < 100.0
• -2^{31} <= n <= 2^{31} - 1
• -10^4 <= x^n <= 10^4

原题链接：：https://leetcode-cn.com/problems/powx-n/ 及 https://leetcode.cn/problems/shu-zhi-de-zheng-shu-ci-fang-lcof/description/

示例

示例 1：

输入：

x = 2.00000, n = 10

输出：

1024.00000

解释：
2^10 = 1024

示例 2：

输入：

x = 2.10000, n = 3

输出：

9.26100

解释：
2.1^3 = 9.261

示例 3：

输入：

x = 2.00000, n = -2

输出：

0.25000

解释：
2^-2 = 1/(2^2) = 0.25

思路解析

本题要求实现一个函数 pow(x, n)，计算 x 的 n 次幂。由于 n 可以是正数、负数或零，且 x 是一个浮点数，因此需要考虑多种情况。为了高效地计算 x^n，可以采用 快速幂算法（也称为 二分幂），其时间复杂度为 O(log n)。

核心思路：

1. 快速幂算法：

   • 利用二分思想，将幂运算拆分为更小的部分。
   • 例如，x^10 可以分解为 (x^5)^2，x^5 又可以分解为 x * (x^2)^2。

2. 处理负指数：

   • 如果 n 为负数，则 x^n = 1 / x^{-n}。
   • 需要特别处理 n 为 -2^{31} 的情况，因为 -n 会超出 32 位整数的范围。

3. 递归与迭代实现：

   • 递归：通过函数调用实现快速幂的分解。
   • 迭代：通过循环实现快速幂，避免递归带来的额外空间开销。

4. 边界条件：

   • 当 n 为 0 时，x^0 = 1。
   • 当 x 为 0 时，0^n 取决于 n 的值，但根据题目限制，x 不会为 0。

具体步骤：

1. 初始化：

   • 如果 n 为 0，直接返回 1。
   • 如果 n 为负数，转换为计算 1 / x^{-n}。需要注意处理 n = -2^{31} 的情况。

2. 快速幂计算：

   • 通过快速幂算法，迭代地将问题规模减半。
   • 如果当前指数为奇数，将结果乘以当前的基数。
   • 每次迭代将基数平方，并将指数右移一位（即除以 2）。

3. 返回结果：

   • 根据 n 的正负返回最终的结果。

复杂度分析：

• 时间复杂度：O(log n)，其中 n 是指数的绝对值。快速幂算法通过每次将问题规模减半，实现了对数级别的时间复杂度。

• 空间复杂度：O(1)，使用常数级别的额外空间。若采用递归实现，则空间复杂度为 O(log n)，由于递归调用栈的深度为 log n。

代码实现

Python 实现

class Solution:
    def myPow(self, x: float, n: int) -> float:
        """
        计算 x 的 n 次幂（x^n）。
        :param x: float - 基数
        :param n: int - 指数
        :return: float - 结果
        """
        if n == 0:
            return 1.0
        
        # 如果 n 是负数，转换为计算 1 / x^{-n}
        if n < 0:
            x = 1 / x
            # 处理 n = -2^31 的情况
            n = -n if n != -2147483648 else 2147483647
        
        result = 1.0
        current_product = x
        current_exponent = n
        
        while current_exponent > 0:
            if current_exponent % 2 == 1:
                result *= current_product
            current_product *= current_product
            current_exponent //= 2
        
        return result

测试代码

以下是针对上述方法的测试代码，使用 unittest 框架进行验证。

import unittest

class Solution:
    def myPow(self, x: float, n: int) -> float:
        """
        计算 x 的 n 次幂（x^n）。
        :param x: float - 基数
        :param n: int - 指数
        :return: float - 结果
        """
        if n == 0:
            return 1.0
        
        # 如果 n 是负数，转换为计算 1 / x^{-n}
        if n < 0:
            x = 1 / x
            # 处理 n = -2^31 的情况
            n = -n if n != -2147483648 else 2147483647
        
        result = 1.0
        current_product = x
        current_exponent = n
        
        while current_exponent > 0:
            if current_exponent % 2 == 1:
                result *= current_product
            current_product *= current_product
            current_exponent //= 2
        
        return result

class TestMyPow(unittest.TestCase):
    def setUp(self):
        self.solution = Solution()

    def test_example1(self):
        x = 2.00000
        n = 10
        expected = 1024.00000
        self.assertAlmostEqual(self.solution.myPow(x, n), expected, places=5, msg="示例1失败")

    def test_example2(self):
        x = 2.10000
        n = 3
        expected = 9.26100
        self.assertAlmostEqual(self.solution.myPow(x, n), expected, places=5, msg="示例2失败")

    def test_example3(self):
        x = 2.00000
        n = -2
        expected = 0.25000
        self.assertAlmostEqual(self.solution.myPow(x, n), expected, places=5, msg="示例3失败")

    def test_zero_exponent(self):
        x = 2.0
        n = 0
        expected = 1.0
        self.assertAlmostEqual(self.solution.myPow(x, n), expected, places=5, msg="零指数测试失败")

    def test_negative_exponent_large(self):
        x = 2.0
        n = -2147483648
        # 由于 n = -2147483648 时，-n 会超出 32 位整数范围，这里仅验证不抛出异常
        result = self.solution.myPow(x, n)
        self.assertTrue(0.0 <= result <= 1.0, "负指数极大测试失败")

    def test_one_base_zero_exponent(self):
        x = 1.0
        n = 0
        expected = 1.0
        self.assertAlmostEqual(self.solution.myPow(x, n), expected, places=5, msg="基数为1且指数为0测试失败")

    def test_one_base_positive_exponent(self):
        x = 1.0
        n = 100
        expected = 1.0
        self.assertAlmostEqual(self.solution.myPow(x, n), expected, places=5, msg="基数为1且正指数测试失败")

    def test_one_base_negative_exponent(self):
        x = 1.0
        n = -100
        expected = 1.0
        self.assertAlmostEqual(self.solution.myPow(x, n), expected, places=5, msg="基数为1且负指数测试失败")

    def test_negative_base_even_exponent(self):
        x = -2.0
        n = 4
        expected = 16.0
        self.assertAlmostEqual(self.solution.myPow(x, n), expected, places=5, msg="负基数偶数指数测试失败")

    def test_negative_base_odd_exponent(self):
        x = -2.0
        n = 3
        expected = -8.0
        self.assertAlmostEqual(self.solution.myPow(x, n), expected, places=5, msg="负基数奇数指数测试失败")

if __name__ == "__main__":
    unittest.main(argv=[''], exit=False)

输出：

..........
----------------------------------------------------------------------
Ran 10 tests in 0.XXXs

OK

复杂度分析

时间复杂度

• 总体复杂度：O(log n)，其中 n 是指数的绝对值。
  • 采用快速幂算法，每次将问题规模减半，因此时间复杂度为对数级别。

空间复杂度

• 总体复杂度：O(1)。
  • 使用常数级别的额外空间。
  • 若采用递归实现，空间复杂度为 O(log n)，由于递归调用栈的深度为对数级别。

结论

通过采用 快速幂算法，我们能够高效地计算一个浮点数 x 的整数次幂 n。该方法利用了幂运算的二分性质，将计算过程中的时间复杂度降低至 O(log n)，同时保持了空间复杂度的最小化。无论 n 是正数、负数还是零，快速幂算法都能准确地计算出结果。

掌握此类快速幂的实现技巧，对于解决各种需要高效幂运算的编程问题具有重要的指导意义，能够在实际编程和算法设计中灵活应用，提高代码的性能和效率。