Pow(x, n)
程序员文章站
2022-05-13 19:31:39
...
Implement pow(x, n), which calculates x raised to the power n (xn).
Example 1:
Input: 2.00000, 10
Output: 1024.00000
Example 2:
Input: 2.10000, 3
Output: 9.26100
该题简单的循环累乘会超时,时间复杂度O(n).不够快!
可以用分治法将复杂度降低到O(logn)
需要注意数值溢出问题!
class Solution {
public:
double myPow(double x, int n) {
return helper(x,n);
}
double helper(double x, long long n)
{
if(n<0) return 1/helper(x,-n);
if (n==0) return 1;
if (n%2==0)
{
double tmp = helper(x,n/2);
return tmp*tmp;
}
else
{
double tmp =helper(x,(n-1)/2);
return tmp*tmp*x;
}
}
};
推荐阅读