0050. Pow(x, n) #

标签：数学、二分查找
难度：中等

题目大意 #

描述：给定浮点数 $x$ 和整数 $n$。

要求：计算 $x$ 的 $n$ 次方（即 $x^n$）。

说明：

$-100.0 < x < 100.0$。
$-2^{31} \le n \le 2^{31} - 1$。
$n$ 是一个整数。
$-10^4 \le x^n \le 10^4$。

示例：

示例 1：

1
2


输入：x = 2.00000, n = 10
输出：1024.00000

示例 2：

1
2
3


输入：x = 2.00000, n = -2
输出：0.25000
解释：2-2 = 1/22 = 1/4 = 0.25

解题思路 #

思路 1：分治算法 #

常规方法是直接将 $x$ 累乘 $n$ 次得出结果，时间复杂度为 $O(n)$。

我们可以利用分治算法来减少时间复杂度。

根据 $n$ 的奇偶性，我们可以得到以下结论：

如果 $n$ 为偶数，$x^n = x^{n / 2} \times x^{n / 2}$。
如果 $n$ 为奇数，$x^n = x \times x^{(n - 1) / 2} \times x^{(n - 1) / 2}$。

$x^{(n / 2)}$ 或 $x^{(n - 1) / 2}$ 又可以继续向下递归划分。

则我们可以利用低纬度的幂计算结果，来得到高纬度的幂计算结果。

这样递归求解，时间复杂度为 $O(\log n)$，并且递归也可以转为递推来做。

需要注意如果 $n$ 为负数，可以转换为 $\frac{1}{x} ^{(-n)}$。

思路 1：代码 #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


class Solution:
    def myPow(self, x: float, n: int) -> float:
        if x == 0.0:
            return 0.0
        res = 1
        if n < 0:
            x = 1/x
            n = -n
        while n:
            if n & 1:
                res *= x
            x *= x
            n >>= 1
        return res

思路 1：复杂度分析 #

时间复杂度：$O(\log n)$。
空间复杂度：$O(1)$。