构建乘积数组

题目描述

给定一个数组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]的值。时间复杂度为O(n2)。

解法二：

如果不考虑除法问题，可以计算出A[0]到A[n-1]的总乘积，B[i]=总乘积/A[i]，但需要考虑A[i]为0的情况。

解法三：

我们可以观察一下数组B的值是怎么来的，假设A.length==4，
B[0]=A[1]A[2]A[3]
B[1]=A[0]A[2]A[3]
B[2]=A[0]A[1]A[3]
B[3]=A[0]A[1]A[2]
我们可以发现，数组Ｂ可以由两部分（绿色和红色）相乘得到，而这两部分均可以表示成阶乘的形式，阶乘意味着可以逐步递推得到，避免了重复计算。可以用C、D两数组代表绿色和红色部分
C[i]=A[0]A[1]…A[i-1]，且C[0]=1
D[i]=A[i+1]A[i+2]…A[n-1]，且D[n-1]=1
于是B[i]=C[i]*D[i]，时间复杂度为O（n）。

public class Solution {
    public int[] multiply(int[] A) {
        if(A == null || A.length == 0)
            return null;
        int[] B = new int [A.length];
        int[] C = new int [A.length];
        int count = 1;
        for(int i = 1; i < B.length; i++) {
            count *= A[i-1];
            B[i] = count;
        }
        count = 1;
        for(int i = C.length - 2; i >= 0; i--) {
            count *= A[i+1];
            C[i] = count;
        }
        B[0] = 1;
        C[C.length - 1] = 1;
        for(int i = 0; i < B.length; i++){
            B[i] = B[i] * C[i];
        }
        return B;
    }
}

代码可以简化，只使用一个辅助数组。