数值的整数次方

题目的主要信息：

• 求一个浮点数的整数次方
• 整数有正有负
• 不可以使用库函数，也不需要判断大数问题

举一反三：

学习完本题的思路你可以解决如下题目：

JZ83. 剪绳子（进阶版）

方法一：直接运算（推荐使用）

思路：

既然是求次方，那我们做不断累乘就可以了，重点是处理负的次方数，因为$x^{-n}=(\frac{1}{x}{)}^{n}x^\{-n\}=(\backslash frac\{1\}\{x\})^n$，因此我们将底数转换为相应分数，就可以将次方数变回正数。

if(exponent < 0){
    base = 1 / base;
    exponent = -exponent;
}

具体做法：

• step 1：先处理次方数为负数的情况，将底数化为分数解决。
• step 2：遍历次方数的次数，不断累乘底数。

Java实现代码：

public class Solution {
    public double Power(double base, int exponent) {
        //处理负数次方
        if(exponent < 0){
            base = 1 / base;
            exponent = -exponent;
        }
        double res = 1.0;
        //累乘
        for(int i = 0; i < exponent; i++)
            res *= base;
        return res;
  }
}

C++实现代码：

class Solution {
public:
    double Power(double base, int exponent) {
        //处理负数次方
        if(exponent < 0){
            base = 1 / base;
            exponent = -exponent;
        }
        double res = 1.0;
        //累乘
        for(int i = 0; i < exponent; i++)
            res *= base;
        return res;
    }
};

Python实现代码：

class Solution:
    def Power(self , base: float, exponent: int) -> float:
        #处理负数次方
        if exponent < 0:
            base = 1 / base
            exponent = -exponent
        res = 1.0
        #累乘
        for i in range(exponent):
            res *= base
        return res

复杂度分析：

• 时间复杂度：$O(n)O(n)$，其中$nn$为所求的次方数，一共需要乘$nn$次
• 空间复杂度：$O(1)O(1)$，常数级变量，无额外辅助空间

方法二：快速幂（扩展思路）

知识点：分治：

分治即“分而治之”，“分”指的是将一个大而复杂的问题划分成多个性质相同但是规模更小的子问题，子问题继续按照这样划分，直到问题可以被轻易解决；“治”指的是将子问题单独进行处理。经过分治后的子问题，需要将解进行合并才能得到原问题的解，因此整个分治过程经常用递归来实现。

思路：

计算幂运算，我们还可以使用快速幂快速计算。 如果我们要计算$5^{10}5^\{10\}$，常规的算法是$5\ast 5=255*5=25$，然后再$25\ast 5=12525*5=125$，如此往下，一共是$99$次运算，即$n-1n-1$次。但是我们可以考虑这样：$5\ast 5=255*5=25$(二次）、$25\ast 25=62525*25=625$（四次）、$625\ast 625=\mathrm{.}\mathrm{.}\mathrm{.}625*625=...$（八次），这是一个二分的思维，运算次数缩减到了$lo{g}_{2}nlog\_2n$次，公式如下：

具体做法：

• step 1：先处理次方数为负数的情况，将底数化为分数解决。
• step 2：使用快速幂计算次方：将已乘出来的部分求次方，可以每次缩小一半要求的次方数。

图示：

Java实现代码：

public class Solution {
    //快速幂
    private double Pow(double x, int y){ 
        double res = 1;
        while(y != 0){
            //可以再往上乘一个
            if((y & 1) != 0) 
                res *= x;
            //叠加
            x *= x; 
            //减少乘次数
            y = y >> 1; 
        }
        return res;
    }
    public double Power(double base, int exponent) {
        //处理负数次方
        if(exponent < 0){
            base = 1 / base;
            exponent = -exponent;
        }
        return Pow(base, exponent);
  }
}

C++实现代码：

class Solution {
public:
    //快速幂
    double Pow(double x, int y){ 
        double res = 1;
        while(y){
            //可以再往上乘一个
            if(y & 1) 
                res *= x;
            //叠加
            x *= x; 
            //减少乘次数
            y = y >> 1; 
        }
        return res;
    }
    double Power(double base, int exponent) {
        //处理负数次方
        if(exponent < 0){
            base = 1 / base;
            exponent = -exponent;
        }
        return Pow(base, exponent);
    }
};

Python实现代码：

class Solution:
    #快速幂
    def Pow(self, x: float, y: int) -> float:
        res = 1
        while y:
            #可以再往上乘一个
            if y & 1: 
                res *= x
            #叠加
            x *= x 
            #减少乘次数
            y = y >> 1 
        return res
        
    def Power(self , base: float, exponent: int) -> float:
        #处理负数次方
        if exponent < 0:
            base = 1 / base
            exponent = -exponent
        res = 1.0
        return self.Pow(base, exponent)

复杂度分析：

• 时间复杂度：$O(lo{g}_{2}n)O(log\_2n)$，其中$nn$为所求的次方数，快速幂相当于对求幂使用二分法
• 空间复杂度：$O(1)O(1)$，常数级变量，无额外辅助空间