LeetCode 数值的整数次方

Question

题目描述

给定一个 double 类型的浮点数 base 和 int 类型的整数 exponent。求 base 的 exponent 次方。

问题解析

这道题算是比较麻烦和难一点的一个了。我这里采用的是二分幂思想，当然也可以采用快速幂。
更具剑指 offer 书中细节，该题的解题思路如下：1.当底数为 0 且指数<0 时，会出现对 0 求倒数的情况，需进行错误处理，设置一个全局变量； 2.判断底数是否等于 0，由于 base 为 double 型，所以不能直接用==判断 3.优化求幂函数（二分幂）。
当 n 为偶数，$$a^n = (a^n/2）_（an/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;
}