LeetCode 50. Pow(x, n)（中）& 剑指offer 面试题16. 数值的整数次方（中）

假定我们已经得到了 \(x ^ n\) 的结果，我们如何得到 \(x ^ {2 \times n}\) 的结果？很明显，我们不需要将 x 再乘 n 次。使用公式 \((x ^ n) ^ 2 = x ^ {2 \times n}\)，我们可以在一次计算内得到 \(x ^ {2 \times n}\) 的值。使用该优化方法，我们可以降低算法的时间复杂度。

题目

实现 pow(x, n) ，即计算 x 的 n 次幂函数。
说明:
-100.0 < x < 100.0
n 是 32 位有符号整数，其数值范围是  $ [−2{31}, 2{31} − 1] $ 。

示例

示例 1:

1
2
输入: 2.00000, 10
输出: 1024.00000

示例 2:

1
2
输入: 2.10000, 3
输出: 9.26100

示例 3:

1
2
输入: 2.00000, -2
输出: 0.25000

解释: 2-2 = 1/22 = 1/4 = 0.25

考察知识点

数学、二分查找、注意负指数的情况

核心思想

方法一、暴力遍历

直接将 \(x\) 连续乘上 \(n\) 次。不推荐。 这里需要考虑 n < 0 的特殊情况。

方法二、快速幂算法（递归） 推荐

假定我们已经得到了 \(x ^ n\) 的结果，我们如何得到 \(x^{2 \times n}\) 的结果？很明显，我们不需要将 x 再乘 n 次。使用公式 \((x ^ n) ^ 2 = x ^ {2 \times n}\)，我们可以在一次计 算内得到 \(x ^ {2 \times n}\)的值。使用该优化方法，我们可以降低算法的时间复杂度。

算法
假定我们已经得到了 \(x ^ {n / 2}\) 的结果，并且我们现在想得到 \(x ^ n\)的结果。我们令 A 是 \(x ^ {n / 2}\) 的结果，我们可以根据 \(n\) 的奇偶性来分别讨论 \(x ^ n\) 的值。如果 \(n\) 为偶数，我们可以用公式 \((x ^ n) ^ 2 = x ^ {2 \times n}\) 来得到 \(x ^ n = A \times A\)。如果 \(n\) 为奇数，那么 \(A \times A = x ^ {n - 1}\)。直观上看，我们需要再乘一次 \(x\) ，即 \(x ^ n = A \times A \times x\)。该方法可以很方便的使用递归实现。我们称这种方法为 "快速幂"，因为我们只需最多 \(O(\log n)\) 次运算来得到 \(x ^ n\)。

方法三、快速幂算法（循环）

我们换一个角度来引入非递归的、循环的快速幂。还是7的10次方，但这次，我们把10写成二进制的形式，也就是 \((1010)_{2}\)。现在我们要计算 \(7^{(1010)_2}\) ，可以怎么做？我们很自然地想到可以把它拆分为\(7^{(1000)_2}\) 和 \(7^{(10)_2}\) . 实际上，对于任意的整数，我们都可以把它拆成若干个 \(7^{(100....)_2}\) 的形式相乘。而这些\(7^{(100....)_2}\) ，恰好就是 \(7^{1}\)、\(7^{2}\)、\(7^{4}\)、\(7^{8}\)……我们只需不断把底数进行平方就可以算出它们。

LeetCode题解

方法四、剑指offer优化版

  1. 用位与运算符替代求余符，判断一个数是否是奇数 if exponent & 1 == 1: # 奇数的二进制表示的最后一位上必然是1 。
  2. 用右移代替除法，代替除以2， half = self.fastPow(base, exponent>>1) 。
  3. 对结果越界进行判断， -2147483648 <= int32 <= 2147483647 。

Python版本

方法一的实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution(object):
    def myPow(self, x, n):
        """
        :type x: float
        :type n: int
        :rtype: float
        """
        if n == 0:
            return 1
        if n < 0:
            x = 1 / x
            n = -n
        ans = 1
        res = 1
        while n:
            if n % 2:
                ans *= x
            n >>= 1
            x *= x
        return ans

时间复杂度：\(O(n)\)
空间复杂度：\(O(1)\)
执行用时 :44 ms, 在所有 Python3 提交中击败了25.92%的用户
内存消耗 :13.5 MB, 在所有 Python3 提交中击败了21.61%的用户

方法二的实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def myPow(self, x: float, n: int) -> float:
        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
        
        N = n
        if N < 0:  # 注意判断N为负数的情况
            x = 1 / x
            N = -N
        return fastPow(x, N)

时间复杂度：\(O(log n)\). 每一次我们使用公式 \((x ^ n) ^ 2 = x ^ {2 * n}\) , \(n\) 都变为原来的一半。因此我们需要至多 \(O(log n)\) 次操作来得到结果。
空间复杂度：\(O(\log n)\)， 每一次计算，我们需要存储 \(x ^ {n / 2}\) 的结果。 我们需要计算 \(O(log n)\) 次，所以空间复杂度为 \(O(\log n)\)。
执行用时 :56 ms, 在所有 Python3 提交中击败了8.21%的用户
内存消耗 :13.4 MB, 在所有 Python3 提交中击败了21.72%的用户

方法三的实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def myPow(self, x: float, n: int) -> float:
        N = n
        if N < n:
            x = 1 / x
            N = -N
        ans = 1
        current_product = x
        i = N
        while i:
            if i % 2 == 1:
                ans *= current_product
            current_product = current_product * current_product
            i //= 2
        return ans

时间复杂度：\(O(\log n)\)， 对每一个 n 的二进制位表示，我们都至多需要累乘 1 次，所以总的时间复杂度为 \(O(\log n)\) 。
空间复杂的：\(O(1)\)， 我们只需要用到 2 个变量来保存当前的乘积和最终的结果 x 。
循环方法实现会超出时间限制。

方法四的实现

实现性能优化的极致

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
import unittest
from typing import List

class Solution:
    def fastPow(self, base, exponent):
        if base == 0: return 0
        if exponent == 0:  return 1
        if exponent == 1:  return base
        # 用右移代替除法
        half = self.fastPow(base, exponent>>1)
        # 溢出判断 -2147483648 <= int32 <= 2147483647
        if abs(half) > 46340.95:  # 2**31 ** 0.5 = 46340.95 
            global is_valid
            is_valid = True
            return 0.0
        # 用位与运算符替代求余符
        if exponent & 1 == 1:  # 奇数的二进制表示的最后一位上必然是1
            res = half * half * base
        else:
            res = half * half
        return res

    def myPow(self, base: float, exponent: int) -> float: 
        """设置全局变量表示是否输入错误
        """
        if base == 0.0 and exponent < 0:
            global is_valid
            is_valid = True
            return 0.0
        
        # 判断指数为负数的情况
        is_negative = False
        if exponent < 0:
            exponent = 0-exponent
            is_negative = True
    
        # 求解幂结果
        res = self.fastPow(base, exponent)
        # 如果是负指数，就要取分数结果。
        if is_negative:
            res = 1 / res

        return float('%.5f'%res)

class TestSolution(unittest.TestCase):
    def setUp(self):
        self.test_class = Solution()

    def test_solution(self):
        inputs = [
            [2, 10], [2.10000, 3], [2.00000, -2],  # 功能测试
            [2, 32], [-2, 31], [-2, 33],           # 边界值的测试
            [0, 1], [0, -2],                       # 特殊样例 0的n次方还是0
        ]
        answers = [1024.00000, 9.26100, 0.25000, "ValueError", -2147483648.0, "ValueError", 0.00000, "ValueError"]
        res = []
        for i in range(len(inputs)):
            global is_valid
            is_valid = False
            tmp = self.test_class.myPow(inputs[i][0], inputs[i][1])
            if is_valid:
                res.append("ValueError")
            else:
                res.append(tmp)
        self.assertEqual(res, answers)
 
    def tearDown(self):
        del self.test_class


if __name__ == "__main__":
    is_valid = False  # 全局变量，用于检测当前计算结果是否异常。
    unittest.main()