題目描述
給定一個數(shù)組A[0,1,...,n-1],請構(gòu)建一個數(shù)組B[0,1,...,n-1],其中B中的元素B[i]=A[0]*A[1]*...*A[i-1]*A[i+1]*...*A[n-1]文兢。不能使用除法抖僵。
時間限制：1秒 空間限制：32768K
解題思路
1嫉嘀、暴力解題：使用雙重循環(huán)賦值毫目，時間復(fù)雜度為O(n^2)
public class Solution {
public int[] multiply(int[] A) {
int[] B=new int[A.length];
for(int i=0;i<A.length;i++){
B[i]=1;
for(int j=0;j<A.length;j++)
if(j!=i) B[i]*=A[j];
}
return B;
}
}
2、前后拆分：將A[0]*A[1]*...*A[i-1]和A[i+1]*...*A[n-1]分為兩部分計算脉执，然后相乘镶摘，時間復(fù)雜度O(n)
記
M[i]=A[0]*A[1]*...*A[i-1]据悔，N[i]=A[i+1]*...*A[n-1]，則B[i]=M[i]*N[i]
- 第一個循環(huán)從左到右將M[i]賦值給B[i]：
B[i]=M[i]艾杏、第二個循環(huán)從右到左將N[i]乘進去：B[i]*=N[i]
public class Solution {
public int[] multiply(int[] A) {
int[] B=new int[A.length];
int tmp=1;
for(int i=0;i<A.length;i++){
B[i]=tmp;
tmp*=A[i];
}
tmp=1;
for(int i=A.length-1;i>=0;i--){
B[i]*=tmp;
tmp*=A[i];
}
return B;
}
}
