本文共 1030 字,大约阅读时间需要 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]。不能使用除法。(注意:规定 B[0] = A[1] * A[2] * … * A[n-1],B[n-1] = A[0] * A[1] * … * A[n-2];)
对于A长度为1的情况,B无意义,故而无法构建,因此该情况不会存在。
我们可以把 B[i]=A[0]*A[1]*A[2]*···*A[i-1]*A[i+1]*···*A[n-1]
看成是两部分的乘积
第一部分是 i 之前的所有项,记为 C[i],即C[i]=A[0]*A[1]*A[2]*···*A[i-1]
第二部分是 i 之后的所有项,记为 D[i],即D[i]=A[i+1]*···*A[n-1]
。
经过这样的分隔后,数组 B 就相当于可以用如下的矩阵来构建,B[i] 为矩阵中第 i 行所有元素的乘积。
由此,我们不难得出相应的规律:首先 B[i]=C[i] * D[i],而 C[i] 可以通过自上而下的顺序进行计算,即 C[i]=C[i-1] * A[i-1],同理,D[i] 可以通过自下而上的顺序进行计算,即 D[i]=D[i+1] * A[i+1]。
public class Solution { public int[] multiply(int[] A) { int[] B = new int[A.length]; B[0] = 1; // 自上而下求左半部分乘积 for(int i = 1; i< A.length; i++) { B[i] = B[i-1] * A[i-1]; } // 自下而上求右半部分乘积,temp 用来保存右半部分乘积 int temp = 1; for(int i = A.length - 2; i >= 0; i--) { temp *= A[i+1]; B[i] *= temp; } return B; }}
转载地址:http://gdjvb.baihongyu.com/