算法:数值的整数次方
题目描述:
给定一个 double 类型的浮点数 base 和 int 类型的整数 exponent。求 base 的 exponent 次方。
问题解析:
这道题算是比较麻烦和难一点的一个了。我这里采用的是二分幂思想,当然也可以采用快速幂。
更具剑指 offer 书中细节,该题的解题思路如下:1.当底数为 0 且指数<0 时,会出现对 0 求倒数的情况,需进行错误处理,设置一个全局变量; 2.判断底数是否等于 0,由于 base 为 double 型,所以不能直接用==判断 3.优化求幂函数(二分幂)。
当 n 为偶数,a^n =(a^n/2)(a^n/2);
当 n 为奇数,a^n = a[1] a[2] * a。时间复杂度 O(logn)
时间复杂度:O(logn)
示例代码:
public class Solution {
boolean invalidInput=false;
public double Power(double base, int exponent) {
//如果底数等于0并且指数小于0
//由于base为double型,不能直接用==判断
if(equal(base,0.0)&&exponent<0){
invalidInput=true;
return 0.0;
}
int absexponent=exponent;
//如果指数小于0,将指数转正
if(exponent<0)
absexponent=-exponent;
//getPower方法求出base的exponent次方。
double res=getPower(base,absexponent);
//如果指数小于0,所得结果为上面求的结果的倒数
if(exponent<0)
res=1.0/res;
return res;
}
//比较两个double型变量是否相等的方法
boolean equal(double num1,double num2){
if(num1-num2>-0.000001&&num1-num2<0.000001)
return true;
else
return false;
}
//求出b的e次方的方法
double getPower(double b,int e){
//如果指数为0,返回1
if(e==0)
return 1.0;
//如果指数为1,返回b
if(e==1)
return b;
//e>>1相等于e/2,这里就是求a^n =(a^n/2)*(a^n/2)
double result=getPower(b,e>>1);
result*=result;
//如果指数n为奇数,则要再乘一次底数base
if((e&1)==1)
result*=b;
return result;
}
}
当然这一题也可以采用笨方法:累乘。不过这种方法的时间复杂度为 O(n),这样没有前一种方法效率高。
// 使用累乘
public double powerAnother(double base, int exponent) {
double result = 1.0;
for (int i = 0; i < Math.abs(exponent); i++) {
result *= base;
}
if (exponent >= 0)
return result;
else
return 1 / result;
}
原文地址:https://blog.csdn.net/AWSDN/article/details/142516811
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!