题目描述

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

样例

输入: 2.00000, 10
输出: 1024.00000

输入: 2.10000, 3
输出: 9.26100

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

说明:

• -100.0 < x < 100.0
• n 是 32 位有符号整数，其数值范围是 [−231, 231 − 1] 。

算法分析

快速幂

• 若n > 0，则通过快速幂计算出 $x^n$ 的值
• 若n < 0，计算出 $x^n$ 后，再算出 $\frac{1}{x^n}$ 的值即可

注意:需要用long类型的num专门存n的绝对值，因为int范围是[-2147483648,2147483647]，若n取到-2147483648取绝对值后变成2147483648会爆int范围

时间复杂度 $O(logn)$

Java 代码

class Solution {
    static double qmi(double a,long k)
    {
        double res = 1;
        while(k > 0)
        {
            if((k & 1) == 1) res *= a;
            k >>= 1;
            a *= a; 
        }
        return res;
    }
    public double myPow(double x, int n) {
        long num = n;
        double t = qmi(x,Math.abs(num));
        if(n < 0) return 1 / t;
        return t;
    }
}