mirror of
https://github.com/ShusenTang/LeetCode.git
synced 2024-09-02 14:20:01 +00:00
40 lines
1.5 KiB
Markdown
40 lines
1.5 KiB
Markdown
# [50. Pow(x, n)](https://leetcode.com/problems/powx-n/)
|
||
# 思路
|
||
实现pow函数。
|
||
最先想到的就是用一个循环不断累乘x，实验发现果然超时了。
|
||
更快的方法就是二分，例如要求`pow(x, 4)`，如果按照刚刚超时的思路的话需要进行3次乘法，但是我们可以先算出`res = pow(x, 2)`，这一步需要1次乘法，然后再
|
||
计算出`pow(x, 4) = res * res`即可得到最终结果，这一步需要1次乘法，总共需要2次乘法，比暴力算法少1次乘法，所以更快。如果n很大的话，这个速度优势就很明显了。即，
|
||
|
||
* n为正偶数：A^n = A^(n/2) * A^(n/2)
|
||
* n为正奇数：A^n = A^(n/2) * A^(n/2) * A
|
||
|
||
根据上面的思路就可以写代码了，需要注意的是n可能为负数，为了统一我们可以先对n取绝对值，然后再用一个helper函数实现上述二分求幂的递归过程。
|
||
|
||
时间复杂度O(logn)
|
||
|
||
注意：对int型的最小的数−2^31取绝对值将会超出int型范围，所以要用long long型。
|
||
|
||
|
||
# C++
|
||
``` C++
|
||
class Solution {
|
||
private:
|
||
double helper(double x, long long n){
|
||
if(n == 1) return x;
|
||
double res = helper(x, n >> 1);
|
||
res *= res;
|
||
if(n & 1) res *= x;
|
||
return res;
|
||
}
|
||
public:
|
||
double myPow(double x, int n){
|
||
if(x == double(0.0)) return x;
|
||
if(n == 0) return double(1.0);
|
||
|
||
double res = helper(x, abs(long(n))); // 必须先把n强转为long long型，这样abs才返回的long long型
|
||
if(n > 0) return res;
|
||
return double(1.0) / res;
|
||
}
|
||
};
|
||
```
|