题目描述
实现函数double Power(double base, int exponent),求base的 exponent次方。
不得使用库函数,同时不需要考虑大数问题。
只要输出结果与答案的绝对误差不超过 $10^-2$ 即视为正确。
注意:
- 不会出现底数和指数同为0的情况
- 当底数为0时,指数一定为正
- 底数的绝对值不超过 10,指数的绝对值不超过 109。
样例
输入:10 ,2
输出:100
输入:10 ,-2
输出:0.01
算法1 快速幂
由于指数是int范围,可能很大,所以需要用快速幂求解
注意:指数为负数时,需要指数取绝对值后,将乘积的倒数作为答案
同时考虑到int负数转正数时可能溢出,在取绝对值的时候考虑转换成long long类型
时间复杂度 $O(logn)$
把指数k拆分成了2二进制,每次只用计算前一个数的平方,最坏logn次平方
C++ 代码
class Solution {
public:
double Power(double base, int exponent) {
typedef long long LL;
bool is_minus = exponent < 0;
double res = 1;
//int的负数比整数多一个数,负数转正数时int会溢出,故指数转换成long long
for(LL k = abs(LL(exponent)); k; k>>=1) //指数取绝对值
{
if(k & 1) res *= base;
base *= base; //转换成base^(2^i)形式
}
if(is_minus) res = 1 / res;
return res;
}
};
算法2 (暴力枚举) Time Limit Exceeded
算法思想
指数分情况讨论
- 等于0:返回1
- 大于0:直接乘
- 小于0:base变成1/base,再乘
时间复杂度
执行指数的绝对值次乘法
C++ 代码
class Solution {
public:
double Power(double base, int exponent) {
double res = 1;
if(exponent == 0) return 1;
else if(exponent > 0)
while(exponent--)
res *= base;
else
{
base = 1 / base;
while(exponent++)
res *= base;
}
return res;
}
};