精品课程网站的建设,乐陵网站制作,worldpress和wordpress,濮阳网站建设哪家好题目描述#xff1a;给定一个数组A[0,1,...,n-1],请构建一个数组B[0,1,...,n-1]。其中B中的元素B[i]A[0] * A[1]... * A[i-1] * A[i1]... * A[n-1]。不能使用除法。解题思路#xff1a;首先#xff0c;仔细理解题意#xff0c;B[i]是A数组所有元素的乘积#xff0c;但是没…题目描述给定一个数组A[0,1,...,n-1],请构建一个数组B[0,1,...,n-1]。其中B中的元素B[i]A[0] * A[1]... * A[i-1] * A[i1]... * A[n-1]。不能使用除法。解题思路首先仔细理解题意B[i]是A数组所有元素的乘积但是没有A[i]项如果没有不能使用除法这一限制我们可以直接将A数组的所有元素相乘得到一个乘积记为res则使用公式B[i] res/A[i]即可得到B这个乘积数组。现在有不能使用除法的限制只能使用其他办法当然一个最直观的办法是每次计算B[i]时都计算A数组中n-1个数字的乘积显然这需要O(n^2)的时间复杂度。仔细分析可以发现这种暴力解法有很多重复的计算我们可以通过一个简单的改变来避免这些重复计算。具体如下我们可以把B[i]A[0]*A[1]*A[2]*···*A[i-1]*A[i1]*···*A[n-1]看成是两部分的乘积第一部分是i之前的所有项记为C[i]即C[i]A[0]*A[1]*A[2]*···*A[i-1]第二部分是i之后的所有项记为D[i]即D[i]A[i1]*···*A[n-1]。经过这样的分隔后数组B就相当于可以用如下的矩阵来构建B[i]为矩阵中第i行所有元素的乘积。由此我们不难得出相应的规律首先B[i]C[i]*D[i]而C[i]可以通过自上而下的顺序进行计算即C[0]1,C[i]C[i-1]*A[i-1],同理D[i]可以通过自下而上的顺序进行计算即D[len-1]1,D[i]D[i1]*A[i1]。代码如下所示第一个for循环从上而下相当于计算C[i]第二个for循环自下而上相当于在C[i]的基础上乘以D[i]。显然时间复杂度为O(n)。public int[] multiply(int[] A) {/*思路分成两部分的乘积第一部分可以自上而下第二部分自下而上*/if(Anull||A.length1)return A;int lenA.length;int[] Bnew int[len]; B[0]1;for(int i1;ilen;i) //第一部分可以自上而下B[i]B[i-1]*A[i-1]; //如何要达到上图排序的效果就需要有这样的通项公式int temp1; //temp用来保存第二部分for(int ilen-2;i0;i--){ //第二部分可以自下而上temptemp*A[i1];B[i]B[i]*temp;}return B;
}
