剑指offer-12、数值的整数次方

题⽬描述

给定⼀个 double 类型的浮点数 base 和 int 类型的整数 exponent 。求 base 的exponent
次⽅。保证 base 和 exponent 不同时为 0 。
示例1:
输⼊：2.00000,3
返回值：8.00000
示例2:
输⼊：2.10000,3
返回值：9.26100
思路及解答

暴力求解

如果使⽤暴⼒解答，那么就是不断相乘，对于负数⽽⾔，则是相除，并且符号取反。

1. public class Solution {
2.         public double Power(double base, int exponent) {
3.                 if (exponent < 0) {
4.                         base = 1 / base;
5.                         exponent = -exponent;
6.                 }
7.                 double result = 1.0;
8.                 for (int i = 0; i < exponent; ++i) {
9.                         result *= base;
10.                 }
11.                 return result;
12.         }
13. }

复制代码

拆解递归

题⽬中的 double 类型不能拆解，但是 int 类型的整数 exponet 可以做点⽂章，我们平时求次⽅的时候，假设有个 x 的 4 次⽅，我们通常是求出⼀个 x 的平⽅数 x^2 ，然后两个 x^2相乘就可以得出 x^4 。
对于xⁿ，可以分解为：

• 如果n为偶数：xⁿ = xⁿ/² * xⁿ/²
  
• 如果n为奇数：xⁿ = x * xⁿ/² * xⁿ/²
  

这⾥思路也⼀样，使⽤递归，同时考虑边界条件。如果指数是负数，则先取反，最后取结果的倒数即可。

1. public double Power(double base, int exponent) {
2.     if (exponent == 0) {
3.         // 指数为0则直接返回1
4.         return 1;
5.     }
6.    
7.     if (base == 0) {
8.         //底数为0直接返回0
9.         return 0;
10.     }
11.    
12.     // 判断指数是否为负数
13.     boolean isNegative = false;
14.     if (exponent < 1) {
15.         exponent = -exponent;
16.         isNegative = true;
17.     }
18.    
19.     double result;
20.     if (exponent % 2 == 1) {
21.             result = base * Power(base, exponent - 1);
22.     } else {
23.         double temp = Power(base, exponent / 2);
24.         result = temp * temp;
25.     }
26.     return isNegative ? (1.0 / result) : result;
27. }

复制代码

• 时间复杂度： O(logn) ，每次计算后规模缩⼩⼀半
  
• 空间复杂度： O(logn) ，递归的时候，栈需要⽤到变量
  

迭代快速幂算法

将指数表示为二进制形式，通过位运算减少乘法次数。例如，计算3¹³（1101₂）可以分解为3⁸ * 3⁴ * 3¹。

1. public double power(double base, int exponent) {
2.     if (exponent == 0) {
3.         // 指数为0则直接返回1
4.         return 1;
5.     }
6.    
7.     if (base == 0) {
8.         //底数为0直接返回0
9.         return 0;
10.     }
11.    
12.     long exp = Math.abs((long)exponent);
13.     double result = 1.0;
14.    
15.     while (exp > 0) {
16.         if ((exp & 1) == 1) { // 当前二进制位为1
17.             result *= base;
18.         }
19.         base *= base; // 平方
20.         exp >>= 1; // 右移一位
21.     }
22.    
23.     return exponent > 0 ? result : 1.0 / result;
24. }

复制代码

Java标准库

1. public double power(double base, int exponent) {
2.     if (exponent == 0) {
3.         // 指数为0则直接返回1
4.         return 1;
5.     }
6.    
7.     if (base == 0) {
8.         //底数为0直接返回0
9.         return 0;
10.     }
11.    
12.     return Math.pow(base, exponent);
13. }

复制代码

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！