66.构建乘积数组（简单）*

考点：本题考查发散思维能力

题目描述：

给定一个数组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];）

思路一：

连乘n-1个数字得到B[i]，时间复杂度为O(n^n)

思路二：

把数组B看成由一个矩阵来创建.png
将乘积分成两项A[0] * A[1] ...A[i-1]和A[i + 1] ... A[n-1]，数组B可以用一个矩阵来创建，B[i]为矩阵中第i行所有元素的乘积。
C[i] = A[0] * A[1] ...A[i-1]
D[i] = A[i + 1] ... A[n-1]
B[i] = C[i] * D[i]
归纳C[i] 的规律
C[0] = 1
C[1] = A[0]
C[2] = A[0] * A[1]
C[3] = A[0] * A[1] * A[2]
...
C[i] = C[i-1] * A[i -1](i >=1)下三角
归纳D[i] 的规律
D[n - 1] = 1
D[n - 2] = A[n -1]
D[n - 3] = A[n - 1] * A[n - 2]
D[i] = D[i + 1]* A[i + 1](i <= n-2)上三角

import java.util.ArrayList;
public class Solution {
    public int[] multiply(int[] A) {
        int[] B = new int[A.length];
        if(A == null || A.length <= 0)
            return null;
        //下三角
        B[0]=1;
        for(int i=1;i<A.length;i++){
            B[i]=B[i-1]*A[i-1];
        }
        //上三角
        int temp = 1;
        for(int i=A.length-1;i>=0;i--){
            B[i]=temp*B[i];
            temp=A[i]*temp;
        }
        return B;
    }
}