3.md

干丫的算法之构建乘积数组（3）

算法薄弱，每天一道算法题，突破自己

题目

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

人话版题目：计算不包括当前 i 在内的其它的乘积

示例：

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

解析

使用三角矩阵解题，复杂度 O(N)

var constructArr = function(a) {
	// 对角型矩阵，数学中的固定公式
	let left = [1]; // 左三角
	for (let i = 1; i < a.length; i++) {
		left[i] = left[i - 1] * a[i - 1];
	}

	let ret = [];
	let right = []; // 右三角
	for (let i = a.length - 1; i >= 0; i--) {
		if (right.length === 0) {
			right[i] = 1;
		} else {
			right[i] = right[i + 1] * a[i + 1];
		}
		ret[i] = left[i] * right[i];
	}
	return ret;
};