[leetcode 50]pow(x,n)

1 题目

Implement pow(x, n).

Hide Tags

 Math Binary Search

 

2 思路

一开始想的是使用二分递归调用。要考虑n为负数的情况。时间是O(log(n))，比调用pow(x,n-1)要快很多。

 

后来看了别人的思路，有一种bit位操作的，空间复杂度O(1)的算法。

 

3 代码

    public double pow(double x, int n) {
        if (n == 0 || x == 1) {
            return 1;
        }
        if(x == -1) return n % 2 == 1 ? -1 : 1;
        boolean isMinus = false;
        if (n < 0) {
            n = -n;
            isMinus = true;
        }
        
        double pow = this.absPow(x, n);
        if (isMinus) {
            return 1/pow;
        }else {
            return pow;
        }
    }
    
    private double absPow(double x, int n) {
        if (n == 1) {
            return x;
        }
        
        double temp = absPow(x, n/2);
        if (n % 2 == 1) {//奇数
            return temp*x*temp;
        }else {
            return temp*temp;
        }
    }

比特位操作的

    public double pow(double x, int n) {
        double res = 1;
        if (n < 0) {
            x = 1/x;
            n = -n;
        }
        while ( n > 0) {
            if (n % 2 == 1) {
                res = res * x;
            }
            x *= x;
            n = n>>1;
            
        }
        return res;
    }