剑指Offer51 构建乘积数组（思维发散题）

给定一个数组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[0]*A[1]*...*A[i-1]*A[i+1]*...*A[n-1]表达式分为两个部分
• C = A[0]*A[1]*...*A[i-1]
• D = A[i+1]*...*A[n-1]
• B[i] = C*D

    public int[] multiply(int[] A) {
        int [] B = new int[A.length];
        B[0] = 1;
        for(int i=1;i<B.length;i++){
            B[i] = B[i-1]*A[i-1];
        }// C
        int temp = 1;
        for(int i=B.length-2;i>=0;i--){
            temp *= A[i+1];
            B[i] *= temp;
        }// C*D
        return B;
    }