构建乘积数组

描述

给定一个数组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]的值可以看作图中的矩阵中每行的乘积。也就是被1分割两边值的乘积。那么就可以分别计算两部分的乘积再把另一部分乘进去。同时可以看到分割后是两个三角，那么可以先计算下（上）三角的值，再将另一个三角乘进去。

public int[] multiply(int[] A) {
        int size = A.length;
        int[] b = new int[size];
        if (size > 0) {
            b[0] = 1;
            // 计算左边
            for (int i = 1; i < size; i++) {
                b[i] = b[i - 1] * A[i - 1];
            }
            // 计算右边
            for (int j = size - 2, temp = 1; j >= 0; j--) {
                temp = temp * A[j + 1];
                b[j] = b[j] * temp;
            }
        }
        return b;
    }