剑指offer-数值的整次方(四种解法)

【数值的整次方】【四种解法（全）】【剑指offer】

题目描述

给定一个 double 类型的浮点数 base 和 int 类型的整数 exponent。求 base 的 exponent 次方。

保证 base 和 exponent 不同时为 0

🔍 关注公众号“心谭博客” / 👉 前往 xxoo521.com

查看更多前端与算法的系列文章，获得更好阅读体验

解法 1: 内置函数

第一反应直接调用库函数。

// 原文地址：https://xxoo521.com/2019-12-31-pow/
// ac地址：https://www.nowcoder.com/practice/1a834e5e3e1a4b7ba251417554e07c00

function Power(base, exponent) {
    return Math.pow(base, exponent);
}

解法 2: 暴力法

将数字 base 连续乘 exponent 次即可。

时间复杂度是 O(N),空间复杂度是 O(1)

// 原文地址：https://xxoo521.com/2019-12-31-pow/
// ac地址：https://www.nowcoder.com/practice/1a834e5e3e1a4b7ba251417554e07c00

function Power(base, exponent) {
    if (exponent === 0) {
        return 1;
    }
    if (exponent === 1) {
        return base;
    }

    const isNegative = exponent < 0; // 是否是负指数
    const absExponent = Math.abs(exponent);
    let result = base;
    for (let i = 1; i < absExponent; ++i) {
        result = result * base;
    }

    return isNegative ? 1 / result : result;
}

解法 3: 二分法

为了方便讨论，假设指数exponent是正数。那么递归式如下：

• 如果exponent是偶数，Power(base, exponent) = Power(base, exponent / 2) * Power(base, exponent / 2)
• 如果exponent是奇数，Power(base, exponent) = base * Power(base, exponent / 2) * Power(base, exponent / 2)

对于负指数exponent的情况，取其绝对值先计算。将最后结果取倒数即可。

时间复杂度是 O(logN)；由于采用递归结构，空间复杂度是 O(logN)。

// 原文地址：https://xxoo521.com/2019-12-31-pow/
// ac地址：https://www.nowcoder.com/practice/1a834e5e3e1a4b7ba251417554e07c00

function Power(base, exponent) {
    const isNegative = exponent < 0; // 是否是负指数
    const result = absPower(base, Math.abs(exponent));
    return isNegative ? 1 / result : result;
}

function absPower(base, exponent) {
    if (exponent === 0) {
        return 1;
    }

    if (exponent === 1) {
        return base;
    }

    const subResult = absPower(base, Math.floor(exponent / 2));
    return exponent % 2 ? subResult * subResult * base : subResult * subResult;
}

解法 4: 位运算

第 3 种解法可以转换为迭代写法。迭代写法和位运算有关。

为了理解，假设 base=3，exponent= 5。那么 5 的二进制是：101。所以，3 的 5 次方可以写成下图的格式：

可以看到，对 base 进行自乘，导致 base 的指数每次都扩大 2 倍。与 exponent 的二进制相对应。

以上图为例，整个算法的流程如下：

• 结果值 result 初始为 1
• base 初始为 3，此时 exponent 的二进制最右位为 1，更新结果为：base * result
• exponent 右移一位。base 进行累乘，base 更新为 3 的 2 次方。由于 exponent 的二进制最右位为 0，不更新结果
• exponent 右移一位。base 进行累乘，base 更新为 3 的 4 次方。此时 exponent 的二进制最右位为 1，更新结果为：base * result
• 结束

代码如下：

// 原文地址：https://xxoo521.com/2019-12-31-pow/
// ac地址：https://www.nowcoder.com/practice/1a834e5e3e1a4b7ba251417554e07c00

function Power(base, exponent) {
    if (exponent === 0) {
        return 1;
    }
    if (exponent === 1) {
        return base;
    }

    const isNegative = exponent < 0; // 是否是负指数
    let absExponent = Math.abs(exponent);
    let result = 1;
    while (absExponent) {
        // 如果exponent最右位是1，将当前base累乘到result
        if (absExponent & 1) {
            result = result * base;
        }

        base = base * base; // base自乘法
        absExponent = Math.floor(absExponent / 2); // exponent右移1位
    }

    return isNegative ? 1 / result : result;
}