构建乘积数组

题目描述：

给定一个数组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, 3, 4, 5] 输出：[120, 60, 40, 30, 24]

分析：

首先计算数组B中每个下标下左侧元素的乘积， 从i=1开始，因为B[0]左侧没有元素： B[1]=A[0] B[2]=B[1]*A[1] B[3]=B[2]*A[2] … B[n-1]=B[n-2]A[n-2] 然后从倒数第二个位置开始计算右侧元素的乘积 B[n-2]*=A[n-1] B[n-3]=A[n-1]*A[n-2] … B[0]=A[n-1]*A[n-2]*…*A[2] B[0]=A[n-1]*A[n-2]*…A[2]*A[1]

public int[] multiply1(int[] A) { int[] B=new int[A.length]; if(A==null||A.length==0) return B; B[0]=1; for(int i=1;i<A.length;i++) { B[i]=B[i-1]*A[i-1]; } int left=1; for(int i=A.length-2;i>=0;i--) { left*=A[i+1]; B[i]*=left; } return B; }