50. Pow(x, n)

Leetcode link

题目简介

/**
 * @param {number} x
 * @param {number} n
 * @return {number}
 */

题目要求我们实现 pow(x, n) 函数，求 x 的 n 次方

最后返回计算结果

解题思路

这题如果直接用循环相乘来算的话复杂度有点高了

优化的方式是，我们进行拆分：把 2^4 拆分为 (2^2)^2

我们使用一个递归函数进行拆分，在最后返回的时候，我们需要留意一下 n 是否为负，如果是的话还需要用 1 除一下

Javascript

/**
 * @param {number} x
 * @param {number} n
 * @return {number}
 */
var myPow = function (x, n) {
    const getPow = (x, n) => {
        if (x === 0) {
            return 0
        }
        if (n === 0) {
            return 1
        }

        let pow = getPow(x, Math.floor(n / 2))
        pow *= pow
        if (n % 2 === 1) {
            pow *= x
        }

        return pow
    }

    const res = getPow(x, Math.abs(n))

    return n > 0 ? res : 1 / res
};

复杂度分析

时间

O(log |n|)

空间

O(log |n|)