构建乘积数组

发表于 | 分类于

说明

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

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

题解

解析、解析2

算法

B[i] = [1..A[i-1]*A[i+1]…n]，A乘积(不包含A[i])

  • 我们可以把[1…x…n]数组以x为分割点，分成左、右两个数组left[1…x-1]和right[x+1…n]
  • 分别求left乘积和right乘积
  • result[i] = left乘积*right乘积
  • left乘积从左往右，right从右往左（简单)
    rigth从左往右的话需要先算出总乘积，再依次除1.2.3.4等，这里不能用除法
    1
    2
    3
    4
    5
    6
    7
    /**
        * 当前元素左边积的数组(对应每个元素)
        *  说明:第一个元素左边是1，第2个元素左边也是1，第三个元素3左边是（1*2）=2，没有左/右元素时以1代替
        * leftArr积[1,1,2,6,24]
        * rightArr积[120,60,20,5,1]
        * res[i] = leftArr[i]*rightArr[i]
        */

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
 * @param {number[]} a
 * @return {number[]}
 */
var constructArr = function(a) {
    /**
     * 1. 求leftSum
     * 2. 求rightSum，顺便计算结果
     */
    let leftSum = [];
    let leftTemp = 1;
    //得到leftSum
    for(let i = 0;i<a.length;i++){
        leftTemp = leftTemp * (i === 0 ? 1 :a[i-1]);
        leftSum.push(leftTemp);
    }
    //计算rightSum，每个数右边的乘积和
    let j = a.length - 1;
    let res = [];
    let rightTemp = 1;
    while(j>=0){
        rightTemp = rightTemp * (j===a.length-1 ? 1 :a[j+1]);
        //res = rightSum[j] => rightTemp  * leftSum[j]
        res[j] = rightTemp * leftSum[j];
        j--;
    }
    return res;
};