Pow(x, n)

题目介绍

LeetCode 50. Pow(x, n)。

复杂度

时间复杂度: O(log2n) , 空间复杂度: O(1)

解题思路

class Solution {
    func myPow(_ x: Double, _ n: Int) -> Double {
        if x == 0 {
            return 1
        }
        if n < 0 {
            return myPow(1/x, -n)
        }
        var x = x
        var n = n
        var res = 1.0
        while n > 0 {
            /**
             根据二分推导，可通过循环 x = x^2 操作，每次把幂从 n 降至 n//2 ，直至将幂降为 0 ；
             设 res=1 ，则初始状态 x^n = x^n * res。在循环二分时，每当 n 为奇数时，将多出的一项 x 乘入 res ，则最终可化至 x^n = x^0 * res  ，返回 res 即可。
             */
            if n & 1 == 1 {
                res *= x
            }
            x *= x
            n >>= 1
        }
        return res
    }
}

**版权声明**

Ivan’s Blog by Ivan Ye is licensed under a Creative Commons BY-NC-ND 4.0 International License.
由叶帆创作并维护的叶帆的博客博客采用创作共用保留署名-非商业-禁止演绎4.0国际许可证。

本文首发于Ivan’s Blog | 叶帆的博客博客（ http://yeziahehe.com ），版权所有，侵权必究。

本文链接：http://yeziahehe.com/2020/06/28/powx-n/