问题
Implement pow(x, n).
例子
pow(8, 8)
16777216
分析
二分法快速幂
要点
- 二分法;
- 注意abs()函数有溢出的风险。例如-2147483648的绝对值为2147483648,实际上已经超出了int的表示范围。最好abs((long long)n).
时间复杂度
O(logn)
空间复杂度
O(logn)
代码
class Solution {
public:
double myPow(double x, int n) {
if (n == 0) return 1;
if (n < 0) return 1.0 / myPowImpl(x, -(long long)n);
else return myPowImpl(x, n);
}
private:
double myPowImpl(double x, long long n) {
if (n <= 1) return x;
double half = myPowImpl(x, n / 2);
if (n & 1) return half * half * x;
else return half * half;
}
};
网友评论