[leetcode] Pow(x, n) | 指数运算

Posted by: lexigrey on: November 4, 2013

• In: leetcode
• 1 Comment

这题太经典了，在amz wiki上见过解法，才知道可以把指数分一半，从O(n)改成O(logn)。有几个要注意的地方：

1. 初中数学不会了。(-2)^(-3) = 1 / (-2)^3。所以正负号还是和指数是否是偶数有关。
2. 不要分四种情况讨论，简洁的代码是如果n<0，则直接/x，因为前面算好half的也是1/something的！
3. 要特别讨论x == 0的情况，因为后面要1/x，不想挂在这吧。

public double pow(double x, int n) {
    if (x == 0)
        return 0;
    return power(x, n);
}
private double power(double x, int n) {
    if (n == 0)
        return 1;
    double left = power(x, n / 2);
    if (n % 2 == 0) {
        return left * left;
    } else if (n < 0) {
        return left * left / x;
    } else {
        return left * left * x;
    }
}

Tags: math