美文网首页
50. Pow(x, n)

50. Pow(x, n)

作者: RobotBerry | 来源:发表于2017-05-06 15:40 被阅读0次

    问题

    Implement pow(x, n).

    例子

    pow(8, 8)
    16777216

    分析

    二分法快速幂

    要点

    • 二分法;
    • 注意abs()函数有溢出的风险。例如-2147483648的绝对值为2147483648,实际上已经超出了int的表示范围。最好abs((long long)n).

    时间复杂度

    O(logn)

    空间复杂度

    O(logn)

    代码

    class Solution {
    public:
        double myPow(double x, int n) {
            if (n == 0) return 1;
            if (n < 0) return 1.0 / myPowImpl(x, -(long long)n);
            else return myPowImpl(x, n);
        }
        
    private:
        double myPowImpl(double x, long long n) {
            if (n <= 1) return x;
            double half = myPowImpl(x, n / 2);
            if (n & 1) return half * half * x;
            else return half * half;
        }
    };
    

    相关文章

      网友评论

          本文标题:50. Pow(x, n)

          本文链接:https://www.haomeiwen.com/subject/uqzetxtx.html