题目描述

[EN | CN]

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

示例 1:

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

示例 2:

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

示例 3:

1
2
3
输入: 2.00000, -2
输出: 0.25000
解释: 2-2 = 1/22 = 1/4 = 0.25

说明:

  • -100.0 < x < 100.0;
  • n 是 32 位有符号整数,其数值范围是 [−2^31, 2^31 − 1]。

解法 1:递归

为了加快速度,其实我们可以利用快速幂来解决,当我们在计算 $x^n$ 的时候,可以先算 $k = x^{\lfloor\frac{n}{2}\rfloor}$:

  • 如果 $n$ 为偶数,那么 $x^n = k^2$;
  • 如果 $n$ 为奇数,那么 $x^n = k^2 \times x$。

根据这个逻辑,使用递归就非常自然了。

这里注意有个数值范围的坑,注意以下两行代码:

1
2
3
4
# 写法一
return k ** 2 * (1 if n % 2 == 0 else x)
# 写法二
return k * k if n % 2 == 0 else k * k * x

看起来差不多,其实第一种写法会报错 OverflowError: (34, 'Result too large'),原因是在计算的过程中 k * k 有可能会溢出,此时我们如果计算 k * k * x 等等都会返回 inf;但如果我们用 k ** 2 那么就会报数值溢出的错误。

假设指数为 $n$,那么

  • 时间复杂度为 $O(\log n)$,快速幂时间复杂度;
  • 空间复杂度为 $O(\log n)$,递归深度。

实现与结果如下:

1
2
3
4
5
6
7
8
9
class Solution:
    def myPow(self, x: float, n: int) -> float:
        if n > 0:
            k = self.myPow(x, n // 2)
            return k * k if n % 2 == 0 else k * k * x
        elif n == 0:
            return 1.0
        else:
            return 1.0 / self.myPow(x, -n)
  • 执行用时:40 ms,在所有 Python3 提交中击败了 72.33% 的用户。
  • 内存消耗:13.7 MB,在所有 Python3 提交中击败了 8.33% 的用户。

解法 2:迭代

我们能不能把解法 1 中的递归改成迭代,从而避免掉来自递归的 $O(\log n)$ 空间复杂度?递归中有个很重要的变化就是当前指数是奇数还是偶数的处理方式不同,如果我们要改成迭代,那我们就应该知道在什么时候应该多乘上一个 $x$,什么时候不需要。

我们尝试分解快速幂中每一步的处理,,例如 $x^{233}$ 可以分解为 $x^{128} \times x^{64} \times x^{32} \times x^{8} \times x^{1}$(233 的二进制形式为 1110 1001),那么在计算上我们就按照以下步骤进行:

  1. 初始化每一步的基 base = x、结果 ret = 1;
  2. 用 233 除以 2,得到 116 余 1,那么我们取当前结果 ret = ret * base(即二进制右数第 1 位为 1),base = base ** 2;
  3. 用 116 除以 2,得到 58 余 0,那么我们结果 ret 不用变(即二进制右数第 2 位为 0),base = base ** 2;
  4. 用 58 除以 2,得到 29 余 0,那么我们结果 ret 不用变(即二进制右数第 3 位为 0),base = base ** 2;
  5. 用 29 除以 2,得到 14 余 1,那么我们取当前结果 ret = ret * base(即二进制右数第 4 位为 1),base = base ** 2;
  6. ……

其实上面基本上就相当于是伪代码了。我们求指数的二进制,然后从右依次往左算,每左移一位,该位表示的基是上一位的 2 倍(例如从 2 到 4);然而又因为这是在指数上算的基,其实是相当于上一位的平方了(例如从 $x^2$ 到 $x^4$)。然后根据该位是否为 1,更新当前结果。

  • 假设指数为 $n$,那么

    • 时间复杂度为 $O(\log n)$,快速幂时间复杂度;
    • 空间复杂度为 $O(1)$,常数空间。

实现与结果如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution:
    def myPow(self, x: float, n: int) -> float:
        if n > 0:
            base, ret = x, 1
            while n != 0:
                if n % 2 == 1:
                    ret *= base
                base, n = base * base, n // 2
            return ret
        elif n == 0:
            return 1.0
        else:
            return 1.0 / self.myPow(x, -n)
  • 执行用时:40 ms,在所有 Python3 提交中击败了 72.33% 的用户。
  • 内存消耗:13.7 MB,在所有 Python3 提交中击败了 8.33% 的用户。
▲