码疯窝

LeetCode 每日一题 — Pow(x, n)

2015/01/15 11:15:27    分类: 日志连载    0人评论 次浏览

Implement pow(x, n).

算法分析: 最简单的算法是直接乘, 时间复杂度为O(n), 但是这样做的话在leetcode上面肯定会超时, 所以我们可以根据 pow(x, n) = pow(x * x, n / 2)的方式来计算, 这样时间复杂度为O(log2n), 但是要注意n的奇偶.

Java:

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

C++:

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

Python:

class Solution:
    # @param x, a float
    # @param n, a integer
    # @return a float
    def pow(self, x, n):
        rst = 1
        if (n == 0):
            return 1
        if (n < 0):
            n = -1 * n
            x = 1 / x
        while(n > 0):
            if (n % 2 == 1):
                rst = rst * x
            n /= 2
            x *= x
        return rst
继续查看有关 日志连载的文章

0个访客评论