剑指Offer #12 数值的整数次方（快速幂）

阳光穿透心脏的1/2处 2023-07-11 11:18 2阅读 0赞

> 题目来源：牛客网-剑指Offer专题  
> 题目地址：[数值的整数次方][Link 1]

### 题目描述 ###

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

保证base和exponent不同时为0

### 题目解析 ###

像这种求  a n a^n an 的题目，第一时间想到的必须是快速幂，时间复杂度  O ( l o g n ) O(logn) O(logn) 妥妥的，别再用那种  O ( n ) O(n) O(n) 算法了。

如果不会快速幂的小伙伴，推荐看看这篇文章： [数论基础之快速幂（详细教程）][Link 2]。

当然，这道题还没有那么简单，和我们平时做的数论题目不一样的是，这里的  n n n 有可能是负数  
设  n n n 为正数，则  − n -n −n 为负数，我们就可以做如下简单处理：  
 a − n = ( a n ) − 1 a^\{-n\}=(a^n)^\{-1\} a−n=(an)−1  
我们先求出  a n s = a ∣ n ∣ ans=a^\{|n|\} ans=a∣n∣ ：

*  如果  n n n 为正数，则  a n s ans ans 就是最终答案；
 *  如果  n n n 为负数，则最终答案为  a n s − 1 ans^\{-1\} ans−1

**代码如下：**

public class Solution { 
        public double Power(double base, int exponent) { 
            int n = Math.abs(exponent);
            double ans = 1;
            while (n != 0) { 
                if (n % 2 == 1) { 
                    ans *= base;
                }
                base *= base;
                n /= 2;
            }
            return exponent > 0 ? ans : (1 / ans);
        }
    }

如果只是为了通过的话，你也可以用下面这种没有灵魂的写法：

public class Solution { 
        public double Power(double base, int exponent) { 
            return Math.pow(base, exponent);
        }
    }

--------------------

如果本文对你有所帮助，要记得点赞哦~

[Link 1]: https://www.nowcoder.com/practice/1a834e5e3e1a4b7ba251417554e07c00?tpId=13&tqId=11165&rp=1&ru=%2Fta%2Fcoding-interviews&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking&tPage=1
[Link 2]: https://blog.csdn.net/weixin_42292229/article/details/86742650