❝
这是一道 「中等难度」 的题
https://leetcode.cn/problems/powx-n/❞
题目
实现 ，即计算 x 的整数 n 次幂函数（即，）。
示例 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/2^2 = 1/4 = 0.25
提示：
-
-
-
n是一个整数 -
要么 x不为零，要么 。 -
题解
这道题的暴力解法就是一个简单的 for 循环，循环 n 次，时间复杂度为 。
double ans = 1;
for(int i = 0; i < n; i++){
ans *= x;
}
暴力解法当然不是最优解，不做考虑。
所以要求得 ，我们只需要知道 即可。
同样的，要求得 ，我们只需要知道 即可。
以此类推，每次只需要求得其中的一半，就可以推导出结果，最终时间复杂度为。
需要注意的点：
-
「边界条件 n == 0」时：直接返回 1。 -
「n < 0」时：转换为 。这里还「需要特别注意的一点是当 时， 会越界」，所以需要特殊处理，我们让 ，这样再使用 n < 0这个条件去处理，就不会越界了。 -
「n 为奇数」的时候：如 , 那么用上面的公式 变为 。计算的结果就会少乘了一个 x， 所以最后需要补乘一个x。
Java 代码实现
class Solution {
public double myPow(double x, int n) {
// 边界条件
if(n == 0){
return 1;
}
// 如果 n 是负数
if(n < 0){
if(n == -(1 << 31)){
return myPow(x, n + 1) / x;
}
return myPow(1 / x, -n);
}
double temp = myPow(x, n / 2);
double ans = temp * temp;
// 如果 n 是奇数
if(n % 2 == 1){
ans = ans * x;
}
return ans;
}
}
Go 代码实现
func myPow(x float64, n int) float64 {
// 边界条件
if n == 0 {
return 1
}
if n < 0 {
if n == -(1 << 31) {
return myPow(x, n + 1) / x
}
return myPow(1 / x, -n)
}
temp := myPow(x, n / 2)
ans := temp * temp
if n % 2 == 1 {
ans = ans * x
}
return ans
}
复杂度分析
-
时间复杂度：。 -
空间复杂度：。
– End –
原文始发于微信公众号（i余数）：【算法题解】37. Pow(x, n)
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/193802.html
