16. 数值的整数次方
1. 描述
实现函数double Power(double base, int exponent)，求base的exponent次方。不得使用库函数，同时不需要考虑大数问题。
2. 例子
示例 1:
输入: 2.00000, 10
输出: 1024.00000
示例 2:
输入: 2.10000, 3
输出: 9.26100
示例 3:
输入: 2.00000, -2
输出: 0.25000
解释: 2-2 = 1/22 = 1/4 = 0.25
3. 说明
- -100.0 < x < 100.0
- n 是 32 位有符号整数，其数值范围是 [$−2^{31}$, $2^{31} − 1$]
4. 题解
n = exp
时间复杂度: O($log_2n$)
空间复杂度: O(1)
快速幂乘法
class Solution
{
public:
// double myPow(double x, int n)
double myPow(double base, int exp)
{
if(base == 1 || exp == 0) return 1;
base = (exp > 0 ? base : 1 / base);
long positiveExp = abs((long)exp);
double result = 1;
while(positiveExp > 0)
{
if(positiveExp & 1) result *= base;
base *= base;
positiveExp >>= 1;
}
return result;
}
};