题目描述（中等难度）

50*. Pow(x, n) - 图1

就是求幂次方。

解法一

求幂次方，用最简单的想法，就是写一个 for 循环累乘。

至于求负幂次方，比如

50*. Pow(x, n) - 图2

，可以先求出

50*. Pow(x, n) - 图3

，然后取倒数，

50*. Pow(x, n) - 图4

，就可以了。

  1. double mul = 1;
  2. if (n > 0) {
  3.     for (int i = 0; i < n; i++) {
  4.         mul *= x;
  5.     }
  6. } else {
  7.     n = -n;
  8.     for (int i = 0; i < n; i++) {
  9.         mul *= x;
  10.     }
  11.     mul = 1 / mul;
  12. }

但这样的话会出问题，之前在29题讨论过，问题出在 n = - n 上，因为最小负数

50*. Pow(x, n) - 图5

取相反数的话，按照计算机的规则，依旧是

50*. Pow(x, n) - 图6

，所以这种情况需要单独讨论一下。

  1. if (n == -2147483648) {
  2.     return 0;
  3. }

当然，这样做的话 -1 ，和 1 也需要单独讨论下，因为他们的任意次方都是 1 或者 -1 。

  1. if (x == -1) {
  2.     if ((n & 1) != 0) { //按位与不等于 0 ，说明是奇数
  3.         return -1;
  4.     } else {
  5.         return 1;
  6.     }
  7. }
  8. if (x == 1.0)
  9.     return 1;

综上，代码就出来了。

  1. public double myPow(double x, int n) {
  2.     if (x == -1) {
  3.         if ((n & 1) != 0) {
  4.             return -1;
  5.         } else {
  6.             return 1;
  7.         }
  8.     }
  9.     if (x == 1.0)
  10.         return 1;
  12.     if (n == -2147483648) {
  13.         return 0;
  14.     }
  15.     double mul = 1;
  16.     if (n > 0) {
  17.         for (int i = 0; i < n; i++) {
  18.             mul *= x;
  19.         }
  20.     } else {
  21.         n = -n;
  22.         for (int i = 0; i < n; i++) {
  23.             mul *= x;
  24.         }
  25.         mul = 1 / mul;
  26.     }
  27.     return mul;
  28. }

时间复杂度：O（n）。

空间复杂度：O（1）。

解法二 递归

对于上边的解法，太慢了。可以优化下，类似于29题的思路。乘法的话，我们不用一次一次的相乘，得到 2 次方后，我们可以直接把 2 次方的结果相乘，就可以得到 4 次方，得到 4 次方的结果再相乘，就是 8 次方了，这样的话就会快很多了。

直接利用递归吧

对于 n 是偶数的情况，

50*. Pow(x, n) - 图7

。

对于 n 是奇数的情况，

50*. Pow(x, n) - 图8

。

  1. public double powRecursion(double x, int n) {
  2.     if (n == 0) {
  3.         return 1;
  4.     }
  5.     //偶数的情况
  6.     if ((n & 1) == 0) { 
  7.         double temp = powRecursion(x, n / 2);
  8.         return temp * temp;
  9.     } else { //奇数的情况
  10.         double temp = powRecursion(x, n / 2);
  11.         return temp * temp * x;
  12.     }
  13. }
  15. public double myPow(double x, int n) {
  16.     if (x == -1) {
  17.         if ((n & 1) != 0) {
  18.             return -1;
  19.         } else {
  20.             return 1;
  21.         }
  22.     }
  23.     if (x == 1.0f)
  24.         return 1;
  26.     if (n == -2147483648) {
  27.         return 0;
  28.     }
  29.     double mul = 1;
  30.     if (n > 0) {
  31.         mul = powRecursion(x, n);
  32.     } else {
  33.         n = -n;
  34.         mul = powRecursion(x, n);
  35.         mul = 1 / mul;
  36.     }
  37.     return mul;
  38. }

时间复杂度：O（log（n）)。

空间复杂度：

当然对于这种递归的解法的话，还有一些其他的思路，参考这里。

递归思路是下边的样子

50*. Pow(x, n) - 图9

， 对于 n 是偶数的情况。

50*. Pow(x, n) - 图10

，对于 n 是奇数的情况，

代码就很好写了。

  1. public double powRecursion(double x, int n) {
  2.     if (n == 0) {
  3.         return 1;
  4.     }
  5.     //偶数的情况
  6.     if ((n & 1) == 0) { 
  7.         return powRecursion(x * x, n / 2);
  8.     } else { //奇数的情况 
  9.         return powRecursion(x * x, n / 2) * x;
  10.     }
  11. }
  13. public double myPow(double x, int n) {
  14.     if (x == -1) {
  15.         if ((n & 1) != 0) {
  16.             return -1;
  17.         } else {
  18.             return 1;
  19.         }
  20.     }
  21.     if (x == 1.0f)
  22.         return 1;
  24.     if (n == -2147483648) {
  25.         return 0;
  26.     }
  27.     double mul = 1;
  28.     if (n > 0) {
  29.         mul = powRecursion(x, n);
  30.     } else {
  31.         n = -n;
  32.         mul = powRecursion(x, n);
  33.         mul = 1 / mul;
  34.     }
  35.     return mul;
  36. }

时间复杂度：O（log（n）)。

空间复杂度：

解法三 迭代

这里介绍种全新的解法，开始的时候受前边思路的影响，一直没理解。下午问同学，同学立刻想到了自己在《编程之美》看到的解法，这里分享下。

以 x 的 10 次方举例。10 的 2 进制是 1010，然后用 2 进制转 10 进制的方法把它展成 2 的幂次的和。

50*. Pow(x, n) - 图11

这样话，再看一下下边的图，它们之间的对应关系就出来了。

50*. Pow(x, n) - 图12

2 进制对应 1 0 1 0，我们把对应 1 的项进行累乘就可以了，而要进行累乘的项也是很有规律，前一项是后一项的自乘。

50*. Pow(x, n) - 图13

。我们可以从最右边一位，开始迭代。看下代码吧。

  1. public double myPow(double x, int n) {
  2.     if (x == -1) {
  3.         if ((n & 1) != 0) {
  4.             return -1;
  5.         } else {
  6.             return 1;
  7.         }
  8.     }
  9.     if (x == 1.0f)
  10.         return 1;
  12.     if (n == -2147483648) {
  13.         return 0;
  14.     }
  15.     double mul = 1;
  16.     if (n > 0) {
  17.         mul = powIteration(x, n);
  18.     } else {
  19.         n = -n;
  20.         mul = powIteration(x, n);
  21.         mul = 1 / mul;
  22.     }
  23.     return mul;
  24. }
  26. public double powIteration(double x, int n) {
  27.     double ans = 1;
  28.     //遍历每一位
  29.     while (n > 0) {
  30.         //最后一位是 1，加到累乘结果里
  31.         if ((n & 1) == 1) {
  32.             ans = ans * x;
  33.         }
  34.         //更新 x
  35.         x = x * x;
  36.         //n 右移一位
  37.         n = n >> 1;
  38.     }
  39.     return ans;
  40. }

时间复杂度：log（n）。

空间复杂度：O（1）。

更新

2020.3.16 更新。感谢 @为爱卖小菜 指出，上边的解法虽然都能 AC，但是以上全错，少考虑了一种情况。

前边我们分析到 -2147483648 需要单独讨论。

但这样的话会出问题，之前在 29题 讨论过，问题出在 n = - n 上，因为最小负数

50*. Pow(x, n) - 图14

取相反数的话，按照计算机的规则，依旧是

50*. Pow(x, n) - 图15

，所以这种情况需要单独讨论一下。

  1. if (n == -2147483648) {
  2.     return 0;
  3. }

但当 n = -2147483648 个时候，并不是所有的

50*. Pow(x, n) - 图16

结果都是 0。

当 x 等于 -1 或者 1 的时候结果是 1 。前边的解法也考虑到了。

下边 x 等于 -1 的时候我们顺便考虑了 n 是其他数的情况，所以没直接返回 1。

  1. if (x == -1) {
  2.     if ((n & 1) != 0) {
  3.         return -1;
  4.     } else {
  5.         return 1;
  6.     }
  7. }
  8. if (x == 1.0f)
  9.     return 1;

但其实 x 是浮点数，我们还少考虑了 -1 到 0 和 0 到 1 之间的数，此时的

50*. Pow(x, n) - 图17

的结果应该是正无穷。

此外 x == 0 的话，数学上是不能算的，这里的话也输出正无穷。

综上，我们的前置条件如下

  1. if (x == -1) {
  2.     if ((n & 1) != 0) {
  3.         return -1;
  4.     } else {
  5.         return 1;
  6.     }
  7. }
  8. if (x == 1.0f){
  9.     return 1;
  10. }
  12. if(n == -2147483648){
  13.     if(x > -1 && x < 1 ){
  14.         return Double.POSITIVE_INFINITY;
  15.     }else{
  16.         return 0;
  17.     }
  18. }

上边就是当 n = -2147483648 的所有情况了。对于

50*. Pow(x, n) - 图18

，x 分成了四种情况。

当 x == -1 结果是 1，上边的代码我们顺便把 n 是其它数的情况也顺便考虑了。

当 x == 1 结果是 1。

当 -1 < x < 1 ，结果是正无穷。

当 x < -1 或者 x > 1 ，结果是 0。

@为爱卖小菜 也提供了一个新方法，可以把上边的所有情况统一起来。

因为当 n = -2147483648 的时候我们无法正确计算，我们可以把

50*. Pow(x, n) - 图19

分解成

50*. Pow(x, n) - 图20

。这样的话两部分都可以成功求解了。

对于解法三，可以改写成下边的样子。其他解法也类似。

  1. public double myPow(double x, int n) {
  2.     double mul = 1; 
  3.     if (n > 0) {
  4.         mul = powIteration(x, n);
  5.     } else {
  6.         //单独考虑 n = -2147483648
  7.         if (n == -2147483648) {
  8.             return myPow(x, -2147483647) * (1 / x);
  9.         }
  10.         n = -n;
  11.         mul *= powIteration(x, n);
  12.         mul = 1 / mul;
  13.     }
  14.     return mul;
  15. }
  17. public double powIteration(double x, int n) {
  18.     double ans = 1;
  19.     //遍历每一位
  20.     while (n > 0) {
  21.         //最后一位是 1，加到累乘结果里
  22.         if ((n & 1) == 1) {
  23.             ans = ans * x;
  24.         }
  25.         //更新 x
  26.         x = x * x;
  27.         //n 右移一位
  28.         n = n >> 1;
  29.     }
  30.     return ans;
  31. }

总

从一般的方法，到递归，最后的解法，直接从 2 进制考虑，每一个数字，都可以转换成 2 的幂次的和，从而实现了最终的解法。

windliang wechat

添加好友一起进步~

如果觉得有帮助的话，可以点击 这里 给一个 star 哦 ^^

如果想系统的学习数据结构和算法，强烈推荐一个我之前学过的课程，可以点击 这里 查看详情