题解 | #数值的整数次方#

题目描述

引用内容
给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。
保证base和exponent不同时为0。不得使用库函数，同时不需要考虑大数问题，也不用考虑小数点后面0的位数。

简而言之就是输入浮点数base，整数n，求base的n次方
示例1:

输入：2.00000,3
返回：8

示例2:

输入：2.00000,-2
返回：0.25000
说明：2的-2次方等于1/4=0.25

解法一：

根据题意我们求base的n次方即是阶乘，这是最先想到的思路，示例1

 public double power(double base,int exponent) {
        double ret =1.0;
        for (int i=0; i<exponent; ++i){
            ret *= base;
        }
        return ret;
    }

但是若是我们输入负数的情况，则不满足题目给出的示例2，所以我们需要考虑负数的情况

 public double power(double base,int exponent) {
        if (exponent < 0) {
            base =1/base;
            exponent = -exponent; //转变成正数
        }
        double resutl =1.0;
        for (int i=0; i<exponent; ++i){
            resutl *= base;
        }
        return resutl;
    }

这种普通求阶乘的方式，就是n * n * n...
时间复杂度：O(n)
空间复杂度：O(1)

解法二：

我们观察这种相乘的过程，比如说我们输入base = 2，n=5 那么就是求2^5

其实可以写成2^1 * 2^2 * 2^2，而且可以知道a^4 = a^2 * a^2
至此高次方的幂可以由低次方的幂相乘得来：5次方 = 2次方 * 2次方 * 本身

    public double Power(double base,int exponent) {
        if(exponent == 1) {
            return base;
        }
        if(exponent > 1) {
            double result =power(base,exponent/2);
            //将拆分出去的结果相乘
            result = result * result;
            return result;
        }
        return 1.0;
    }

此时我们的高次幂的结果由低次幂相乘而来，但是还需要考虑负数和偶数的情况

public class Solution {
     public double Power(double base, int exponent) {
        if (exponent <0){
            base = 1 / base;
            exponent = -exponent;
        }

        if (exponent == 1) {
            return base;
        }

        if (exponent > 1) {
            double result =Power(base, exponent / 2);
            if ((exponent & 1) == 1) { // exp&1就是判断奇偶，=1为奇数，比%效率更高
                result = result * result * base;
            } else {
                //将拆分出去的结果相乘
                result = result * result;
            }
            return result;
        }
        return 1.0;
    }
}

时间复杂度：O(logn)，因为每次减少了一半(n/2)
空间复杂度：O(logn)，因为高次幂由低次幂相乘而来，所以需要记录每次相乘次数