题目描述

题目链接

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

样例

1
2
3
4
示例 1：

输入：x = 2.00000, n = 10
输出：1024.00000
1
2
3
4
示例 2：

输入：x = 2.10000, n = 3
输出：9.26100
1
2
3
4
5
示例 3：

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

算法1

(快速幂) $O(logn)$

如果每次乘以一个 x 来求 x 的 n 次幂的话，那么需要线性的时间，当 n 特别大时，明显效率过低，因此可以二进制的思想将 n 预处理

思路：

  • 借助二进制的思想， n 的二进制表示就表明了 n 可以由 2 的多少次幂组成，那么我们可以预处理 $2^0, 2^1, 2^2 …. $
  • 整体的时间复杂度将会缩减至 $logn$

C++ 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    double myPow(double x, int n) {
        typedef long long LL;
        bool is_minus = n < 0; // 如果幂为负数， 先按照正数计算最后求其倒数即可
        double res = 1;
        for( LL k = abs((LL) n); k ; k >>= 1) // 从 k 的第零位开始枚举，看当前位置是否为 1，若为1则应乘上 x^(2^i)
        {
            if( k & 1) 
                res *= x;
            x *= x;
        }

        if( is_minus) res = 1 / res;

        return res;
    }
};