0050. Pow(x, n)

0050. Pow(x, n) #

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

题目大意 #

给定浮点数 x 和整数 n,计算 $x^n$。

解题思路 #

常规方法是直接将 x 累乘 n 次得出结果,时间复杂度为 $O(n)$。可以利用快速幂来减少时间复杂度。

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

$x^(n/2)$ 又可以继续向下递归划分。则我们可以利用低纬度的幂计算结果,来得到高纬度的幂计算结果。

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

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

代码 #

 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
本站总访问量  次  |  您是本站第  位访问者