当前位置: 首页 > >

乘积数组

发布时间:

题目描述

给定一个数组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[i]值为除A[i]值的乘积,那么就另A[i]值为11;(但时间复杂度O(n2))




import java.util.ArrayList;
public class Solution {
public int[] multiply(int[] A) {
int[] B = new int[A.length];
boolean changed = false;
for(int k = 0; k < B.length; k++){
B[k] = 1;
for(int i = 0; i < A.length; i++){
int temp = 1;
if(i == k){
changed = true;
temp = A[i];
A[i] = 1;
}
B[k] *= A[i];
if(changed){
A[i] =temp;
changed = false;
}
}

}
return B;
}
}

第二种方法:计算A[i]左边的乘积? ? 在乘右边的乘积 时间复杂度O(n)


?


import java.util.ArrayList;
public class Solution {
public int[] multiply(int[] A) {

int length = A.length;
int[] B = new int[length];
if(length != 0 ){
B[0] = 1;
//计算下三角连乘
for(int i = 1; i < length; i++){
B[i] = B[i-1] * A[i-1];
}
int temp = 1;
//计算上三角
for(int j = length-2; j >= 0; j--){
temp *= A[j+1];
B[j] *= temp;
}
}
return B;

}
}

?


?


?



友情链接: