536，剑指 Offer-构建乘积数组

Original 博哥数据结构和算法 2022-05-01

收录于合集 #剑指offer 34个

By its very nature, history is always a one-sided account.

就其本质而言，历史始终是一面之词。

问题描述

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

两边分别相乘

这题要求的是每个元素的值是除自己以外其他所有元素的乘积。最简单的一种方式就是把所有元素都相乘，然后再用这个乘积除以每一个元素即可。但题中要求的是不能使用除法，所以这种方式是行不通的。

如果我们能计算每个元素左边所有元素的乘积和右边所有元素的乘积，只需要把他们相乘就可以满足这题的要求，就像下面这样，如果我们要求元素4的值

代码如下

 1public int[] constructArr(int[] a) {
 2    //边界条件判断
 3    if (a == null || a.length == 0)
 4        return a;
 5    int length = a.length;
 6    //每个元素左边所有元素的乘积
 7    int[] resLeft = new int[length];
 8    //每个元素右边所有元素的乘积
 9    int[] resRight = new int[length];
10    //两个默认值
11    resLeft[0] = 1;
12    resRight[length - 1] = 1;
13
14    //当前元素左边的所有元素乘积（不包含当前元素）
15    for (int i = 1; i < length; i++) {
16        resLeft[i] = resLeft[i - 1] * a[i - 1];
17    }
18    //当前元素右边的所有元素乘积（不包含当前元素）
19    for (int i = length - 2; i >= 0; i--) {
20        resRight[i] = resRight[i + 1] * a[i + 1];
21    }
22    //左边乘以右边就是我们要求的结果
23    int[] res = new int[length];
24    for (int i = 0; i < length; i++) {
25        res[i] = resLeft[i] * resRight[i];
26    }
27    return res;
28}

代码优化

上面代码中有3个for循环，其中第2个可以和第3个合并，来看下代码。

 1public int[] constructArr(int[] a) {
 2    //边界条件的判断
 3    if (a == null || a.length == 0)
 4        return a;
 5    int length = a.length;
 6    int[] res = new int[length];
 7    res[0] = 1;
 8    //当前元素左边的所有元素乘积（不包含当前元素）
 9    for (int i = 1; i < length; i++) {
10        res[i] = res[i - 1] * a[i - 1];
11    }
12    int right = 1;
13    //right表示当前元素右边所有元素的乘积（不包含当前元素）,
14    //res[i]表示的是左边的乘积，他俩相乘就是
15    //除了自己以外数组的乘积
16    for (int i = length - 1; i >= 0; i--) {
17        res[i] *= right;
18        right *= a[i];
19    }
20    return res;
21}