50. Pow(x, n)
实现 pow(x, n) ,即计算
x
的整数n
次幂函数(即,xn
)。示例 1:
输入:x = 2.00000, n = 10 输出:1024.00000示例 2:
输入:x = 2.10000, n = 3 输出:9.26100示例 3:
输入:x = 2.00000, n = -2 输出:0.25000 解释:2-2 = 1/22 = 1/4 = 0.25提示:
-100.0 < x < 100.0
-2^31 <= n <= 2^31-1
n
是一个整数- 要么
x
不为零,要么n > 0
。-10^4 <= x^n <= 10^4
基本思路
myPow
函数的目的是计算 x
的 n
次幂,即 x^n
。为了优化计算,代码使用了递归和分治法,将指数的计算分成较小的子问题来解决,从而减少计算次数。
代码分析
-
基准情况
- 如果
n
等于 0,任何数的 0 次幂都是 1。 - 如果
n
等于 1,x
的 1 次幂就是x
本身。 - 如果
n
等于 -1,x
的 -1 次幂就是1 / x
。
- 如果
-
递归调用
- 将
n
分成两部分进行递归计算,计算x
的n/2
次幂。
- 将
-
合并结果
- 如果
n
是偶数,x^n
就等于x^(n/2) * x^(n/2)
。 - 如果
n
是奇数,则根据n
的正负情况处理:- 对于负指数
n < 0
,x^n
等于x^(n/2) * x^(n/2) * (1/x)
。 - 对于正指数
n > 0
,x^n
等于x^(n/2) * x^(n/2) * x
。
- 对于负指数
- 如果
递归的效率
这种方法的效率比直接循环计算所有次幂要高,因为它将问题规模减小了一半。时间复杂度为 O(log n),因为每次递归调用都将 n
减小了一半。这比简单的 O(n) 循环要高效得多。
class Solution {public double myPow(double x, int n) {if (n == 0) {return 1;}if (n == 1) {return x;}if (n == -1) {return 1 / x;}double half = myPow(x, n / 2);if (n % 2 == 0) {return half * half;} else {if (n < 0) {return half * half * (1 / x);} else {return half * half * x;}}}
}