构建乘积数组

题目

给定一个数组A[0,1,...,n-1],请构建一个数组B[0,1,...,n-1],其中B中的元素B[i]&＃61;A[0]*A[1]*...*A[i-1]*A[i&＃43;1]*...*A[n-1]。不能使用除法。

思路

   观察下公式&＃xff0c;你会发现&＃xff0c;B[i]公式中没有A[i]项&＃xff0c;也就是说如果可以使用除法&＃xff0c;就可以用公式B[i]&＃61;A[0]*A[1]*.....*A[n-1]/A[i]来计算B[i]&＃xff0c;但是题目要求不能使用&＃xff0c;因此我们只能另想办法。

现在要求不能使用除法&＃xff0c;只能用其他方法。一个直观的解法是用连乘n-1个数字得到B[i]。显然这个方法需要O(n*n)的时间复杂度。

好在还有更高效的算法。可以把B[i]&＃61;A[0]*A[1]*.....*A[i-1]*A[i&＃43;1]*.....*A[n-1]。看成A[0]*A[1]*.....*A[i-1]和A[i&＃43;1]*.....A[n-2]*A[n-1]两部分的乘积。

即通过A[i]项将B[i]分为两部分的乘积。效果如下图所示&＃xff1a;

不妨设定C[i]&＃61;A[0]*A[1]*...*A[i-1]&＃xff0c;D[i]&＃61;A[i&＃43;1]*...*A[n-2]*A[n-1]。C[i]可以用自上而下的顺序计算出来&＃xff0c;即C[i]&＃61;C[i-1]*A[i-1]。类似的&＃xff0c;D[i]可以用自下而上的顺序计算出来&＃xff0c;即D[i]&＃61;D[i&＃43;1]*A[i&＃43;1]。

如果还是不明白&＃xff0c;没有关系&＃xff0c;直接看下代码&＃xff0c;细细体会下就懂了。

第一个for循环用来计算上图1范围的数&＃xff0c;第二个for循环用来计算上图2范围的数。

public static int[] multiply(int[] A) {if(A &＃61;&＃61; null || A.length &＃61;&＃61;0){return A;}int length &＃61; A.length;int [] B &＃61; new int[length];B[0] &＃61; 1;// 先计算左下三角形&＃xff0c;此时B[0]只有一个元素&＃xff0c;舍为1&＃xff0c;// B[0]不包括A[0]for (int i &＃61; 1; i &＃61;0; i--) {//最终的B[i]是之前乘好的再乘以右边的B[i] *&＃61;tmp;tmp *&＃61; A[i];}return B;}