LeetCode 50 Pow(x,n)

LeetCode50 Pow(x,n)

题目描述

实现 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

算法分析

• 快速幂
  

时间复杂度

\(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;
    }
}