50. powx n
难度:Medium
刷题内容
原题连接
- https://leetcode.com/problems/powx-n/
内容描述
mplement 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
Example 3:
Input: 2.00000, -2
Output: 0.25000
Explanation: 2-2 = 1/22 = 1/4 = 0.25
Note:
-100.0 < x < 100.0
n is a 32-bit signed integer, within the range [?2^31, 2^31 ? 1]
思路1 **- 时间复杂度: O(lgN)*- 空间复杂度: O(1)***
求一个数的n次方是我们经常用的函数，一般刚开始可能会用暴力的方法去求，做了n次循环，但由于这里的n非常大，单纯的暴力会TLE，这里可以用分治的思想，比如2*2*2*2，我们前面已经计算过2*2了，那么后面就不用再计算依次，就相当于2*2*（2*2）,这样时间复杂度就变成了lgN，接下来只要主要幂次是负数的情况即可
class Solution {
public:
double Pow(double x, long long n)
{
if(!n)
return 1;
if(n == 1)
return x;
double temp = Pow(x,(n)/ 2);
double ret;
if(n&1)
ret = temp * temp * x;
else
ret = temp * temp;
return ret;
}
double myPow(double x, int n) {
long long k = n;
if(n < 0)
x = 1 / x;
return Pow(x,n);
}
};
