剑指Offer第五十一题：构建乘积数组

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

思路：这题主要是如何减少复杂程度；本来B[i]=B[i-1]A[i]/A[i-1],但是不能用除法，那么可以考虑分割开来算，先算前一半A[1]*A[2]...A[i-1]，再算后一半A[i+1]..*A[n-1]，然后相乘即为最后答案.前一段的规律就是后一个数等于前一个数乘上A[i-1],后一段相似，把它反过来可以避免除法；
public class Q_51 {

public int[] multiply(int[] A) {
    int[] first = new int[A.length];
    int[] back = new int[A.length];
    first[0] = back[0] = 1;
    for (int i = 1; i < A.length; i++) {
        first[i] = first[i - 1] * A[i - 1];
        back[i] = back[i - 1] * A[A.length - i];
    }
    int[] B = new int[A.length];
    for (int j = 0; j < A.length; j++) {
        B[j] = first[j] * back[A.length - j - 1];
    }
    return B;
}
public static void main(String[] args) {
    int[] A = {1, 2, 3, 4};
    System.out.println(Arrays.toString(new Q_51().multiply(A)));
}

}