实现 pow(x, n) ，即计算 x 的 n 次幂函数。

示例 1:

输入: 2.00000, 10
输出: 1024.00000

示例 2:

输入: 2.10000, 3
输出: 9.26100

示例 3:

输入: 2.00000, -2
输出: 0.25000
解释: 2-2 = 1/22 = 1/4 = 0.25

说明:

  • -100.0 < x < 100.0
  • n 是 32 位有符号整数，其数值范围是 [−231, 231 − 1] 。
Related Topics
  • 数学
  • 二分查找
    • \n
  • 👍 533
  • 👎 0
    1. 第一种解法：快速幂+递归
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    public double myPow(double x, int n) {
       int N = n;
       return n >= 0 ? quickMUl(x, N) : 1.0/quickMUl(x, N);

    }

    public double quickMUl(double x, int N){
       if(N == 0){
          return 1.0;
       }
       double y = quickMUl(x, N / 2);
       return  N%2 == 0 ? y*y : y*y*x;
    }

    时间复杂度 ：O(logn) 递归的层数

    空间复杂度：O(logn) 递归的层数

    1. 快速幂+迭代

      从下列公式推算：
      $$
      n=2^{i_0}+2^{i_1}+\cdots+2^{i_k}
      $$
      可以得知

      $$
      x^n=x^{2^{i_0}}*x^{2^{i_1}}\cdotsx^{2^{i_k}}
      $$

      所以我们的代码可以改成这样：

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      double quickMul(double x, long N) {
      		double ans = 1.0;
      		// 贡献的初始值为 x
      		double x_contribute = x;
      		// 在对 N 进行二进制拆分的同时计算答案
      		while (N > 0) {
      			if (N % 2 == 1) {
      				// 如果 N 二进制表示的最低位为 1，那么需要计入贡献
      				ans *= x_contribute;
      			}
      			// 将贡献不断地平方
      			x_contribute *= x_contribute;
      			// 舍弃 N 二进制表示的最低位，这样我们每次只要判断最低位即可
      			N /= 2;
      		}
      		return ans;
      	}

      	public double myPow(double x, int n) {
      		long N = n;
      		return N >= 0 ? quickMul(x, N) : 1.0 / quickMul(x, -N);
      	}

      时间复杂度：O(logn)

      空间复杂度：O(1)