題目描述

給定一個(gè)數(shù)組A[0,1,...,n-1],請(qǐng)構(gòu)建一個(gè)數(shù)組B[0,1,...,n-1],其中B中的元素B[i]=A[0]*A[1]*...*A[i-1]*A[i+1]*...*A[n-1]。不能使用除法。

時(shí)間限制：1秒 空間限制：32768K

解題思路

1、暴力解題：使用雙重循環(huán)賦值，時(shí)間復(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]分為兩部分計(jì)算，然后相乘，時(shí)間復(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]

• 第一個(gè)循環(huán)從左到右將M[i]賦值給B[i]：B[i]=M[i]、第二個(gè)循環(huán)從右到左將N[i]乘進(jìn)去：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;
    }
}