JavaScript实现构建乘积数组

题目描述

给定一个数组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]。不能使用除法。

实现思路

既然不能用乘法，分析题目，我们可以将乘积拆为两项。即:

C[i] = A[0] * A[1] *...*A[i-1]
D[i] = A[i + 1] *...* A[n-1]
B[i] = C[i] * D[i]

我们先来计算C[i]，使用数学归纳法：

C[0] = 1
C[1] = A[0]
C[2] = A[0] * A[1]
C[3] = A[0] * A[1] * A[2]
...

我们可以得出规律：C[i] = C[i-1] * A[i -1](i >=1)
我们继续用数学归纳法计算D[i]:

D[n - 1] = 1
D[n - 2] = A[n -1]
D[n - 3] = A[n - 1] * A[n - 2]

我们可以得出规律：D[i] = D[i + 1]* A[i + 1](i <= n-2)

JavaScript代码实现如下：

function multiply(array)
{
    let res = [];
    if(Array.isArray(array) && array.length > 0) {
        res[0] = 1;
        // 计算C[i]
        for(let i = 1; i < array.length; i++) {
            res[i] = res[i -1] * array[i - 1];
        }
        // 计算D[i]
        for(let j = array.length - 2, temp = 1; j >= 0; j--) {
            temp *= array[j + 1];
            res[j] *= temp;
        }
        return res;
    }
}