Lexi's Leetcode solutions

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

Posted on: November 4, 2013

这题太经典了,在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;
    }
}
Advertisements
Tags:

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: