剑指Offer题解 - Day52

剑指 Offer 66. 构建乘积数组

力扣题目链接[1]

给定一个数组 A[0,1,…,n-1]，请构建一个数组 B[0,1,…,n-1]，其中 B[i] 的值是数组 A 中除了下标 i 以外的元素的积, 即 B[i]=A[0]×A[1]×…×A[i-1]×A[i+1]×…×A[n-1]。不能使用除法。

「示例:」

输入: [1,2,3,4,5]
输出: [120,60,40,30,24]

「提示：」

• 所有元素乘积之和不会溢出 32 位整数
• a.length <= 100000

思路：

首先考虑暴力法求解。题目没有限制使用乘法，因此可以分别进行相乘获取结果数组。

暴力法

不难写出如下代码：

/**
 * @param {number[]} a
 * @return {number[]}
 */
var constructArr = function(a) {
    let res = [];
    for (let i = 0; i < a.length; i++) {
        let temp = 1;
        let j = 0;
        while(j < a.length) {
            if (j !== i) temp *= a[j];
            j++;
        }
        res.push(temp);
    }
    return res;
};

• 时间复杂度 O(n^2)。
• 空间复杂度 O(n)。

分析：

暴力法需要双层遍历，效率太低，而且无法通过提交。因此本方法不推荐使用，了解即可。

那如何才不需要双层遍历，同时不使用除法进行题解呢？双层遍历的效率低是因为没有合理利用重复相乘所得到的结果。

假设结果数组是每个元素相乘，然后当前元素置为 「1」 ，那么就可以组成一个如下的列表：

// 假设数组为[1,2,3,4,5]

1 2 3 4 5
1 1 3 4 5
1 2 1 4 5
1 2 3 1 5
1 2 3 4 1

分别迭代计算 「下三角」 和 「上三角」 两部分的乘积，就可以得出最终结果。

前缀和

/**
 * @param {number[]} a
 * @return {number[]}
 */
var constructArr = function(a) {
    let length = a.length; // 缓存数组的长度
    if (!length) return []; // 如果数组为空，则直接返回空数组
    let b = Array.from({ length }); // 初始化指定长度的数组
    b[0] = 1;
    let temp = 1;
    for (let i = 1; i < length; i++) { // 计算下三角
        b[i] = b[i - 1] * a[i - 1];
    }
    for (let i = length - 2; i >= 0; i--) { // 计算上三角
        temp *= a[i + 1];
        b[i] *= temp;
    }
    return b;
};

• 时间复杂度 O(n)。
• 空间复杂度 O(1)。

分析：

该方法的难点在于如何计算下三角和上三角。同时避免计算a[i] 。

首先来看下三角。初始化b[0] = 1，然后计算b[1]及以后的值。计算方式就是用b[i - 1]来存储上一次循环的乘积。使用存储的乘积再乘以a[i - 1]，再赋值给b[i]本身。下三角循环完毕后，b数组里存储的就是下三角元素的乘积。

再来看上三角。因为我们要避开a[i]，因此这里默认从倒数第二个元素开始循环。而且下三角已经将b元素的最后一项计算正确了。使用变量temp来保存上三角的乘积。累计相乘后，每次循环的最后再将存储的乘积与b数组当前元素进行相乘，最后得到的值就是最终结果。

计算完毕后，返回数组b。

总结

本题考查数学中的前缀和。核心原理就是存储前面计算好的乘积结果，防止大量的重复计算。同时要注意两次循环的下标初始值和a数组的下标取值。

复杂度方面，遍历了两次数组a，因此时间复杂度是O(n) 。声明了常数级别的常量，b 数组是返回值，因此不计算复杂度，所以空间复杂度是O(1) 。

参考资料

[1]

力扣题目链接: https://leetcode-cn.com/leetbook/read/illustration-of-algorithm/57d8cm/