吴师兄学算法

# 剑指 Offer 66. 构建乘积数组

# 一、题目描述

给定一个数组 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

# 二、题目解析

按照正常的思路，既然 B[i]=A[0]×A[1]×…×A[i-1]×A[i+1]×…×A[n-1]，那么想要计算出 B[i] 来那每次都去遍历数组 A，把这些数字相乘就行了。

而数组 B 的长度为 n，并且计算数组 B 中的每个元素时都需要完整的遍历一遍数组 A，而数组 A 的长度为 n，那么整体的时间复杂度就达到了 O(N(2)) 级别，按照这个逻辑写出的代码提交会超时。

那么哪里可以优化呢？

上面的暴力解法中充斥着大量重复的计算！

比如数组 A 为 [1,2,3,4,5] 。

1、想要计算除了 2 以外的结果时，需要计算 1 * 3 * 4 * 5。

2、想要计算除了 3 以外的结果时，需要计算 1 * 2 * 4 * 5。

注意到，这两个计算过程都计算了 1 和 4 * 5 。

所以，我们优化的方向就是去保存好计算的结果，避免重复计算。

1 出现在 2 和 3 的左侧，4 * 5 出现在 2 和 3 的右侧，它们分别可以使用数组提前计算保存下来。

在公式 B[i]=A[0]×A[1]×…×A[i-1]×A[i+1]×…×A[n-1] 中，实际上可以划分为两个部分，从 0 到 i - 1 和从 i + 1 到 n - 1，因此，想要构建乘积数组后某下标对应元素的值，只需要求出该下标对应原数组中其左边的元素的乘积和其右边的元素的乘积，最后将两个乘积再相乘即可。

具体操作如下：

数组 A 为 [1,2,3,4,5] 。

1、数组 left[i] 表示在数组 A 中下标为 i 的所有左边元素的乘积，如果左边没有元素，默认为 1。

2、数组 right[i] 表示在数组 A 中下标为 i 的所有右边元素的乘积，如果右边没有元素，默认为 1。

3、B[i] = left[i] * right[i] 。

img

img

# 三、参考代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 剑指 Offer 66. 构建乘积数组:https://leetcode-cn.com/problems/gou-jian-cheng-ji-shu-zu-lcof/
class Solution {
    public int[] constructArr(int[] a) {

        // 边界判断
        if( a == null || a.length == 0 ) return a;

        // 获取数组 a 的长度
        int length = a.length;

        // 数组 leftA 表示数组 a 中每个元素左边所有元素的乘积
        // 比如 left[5] 表示数组 a 中下标为 5 的元素的左边所有元素的乘积
        // 即 left[5] = a[0] * a[1] * a[2] * a[3] * a[4]
        int[] leftA = new int[length];

        // 数组 rightA 表示数组 a 中每个元素右边边所有元素的乘积
        // 比如 rightA[3] 表示数组 a 中下标为 3 的元素的右边边所有元素的乘积
        // 即 rightA[3] =  a[4] * a[5]
        int[] rightA = new int[length];

        // 由于任何数与 1 相乘都是它本身，因此，如果发现元素左边没有元素时，默认值为 1
        // 这样就不会影响到后面的计算
        leftA[0] = 1;
        
        // 由于任何数与 1 相乘都是它本身，因此，如果发现元素右边没有元素时，默认值为 1
        // 这样就不会影响到后面的计算
        rightA[length - 1] = 1;

        // 开始不断填充 leftA
        for( int i = 1 ; i < length ; i++ ){
            leftA[i] = leftA[ i - 1 ] * a[ i - 1 ];
        }

        // 开始不断填充 rightA
        for( int j = length - 2 ; j >= 0 ; j-- ){
            rightA[j] = rightA[ j + 1 ] * a[ j + 1 ];
        }

        // 数组 B 存放结果
        int[] B = new int[length];

        // 只求出该下标对应原数组中其左边的元素的乘积和其右边的元素的乘积
        // 最后将两个乘积再相乘即可
        for( int k = 0 ; k < length ; k++){
            B[k] = leftA[k] * rightA[k];
        }

        // 返回数组 B
        return B;

    }
}

# 四、时间复杂度

1、时间复杂度 O(N) ： 其中 N 为数组长度，三轮遍历数组 a ，使用 O(N) 时间。

2、空间复杂度 O(N) ： 额外创建了两个数组

← LeetCode 697、数组的度 →