【剑指Offer】构建乘积数组

Posted on | In ,

题目

给定一个数组A[0, 1, … , n-1]，请构建一个数组B[0, 1, … , n-1]，其中B中的元素B[i]=A[0]xA[1]x…xA[i-1]xA[i+1]x…xA[n-1]。不能使用除法。

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public int[] multiply(int[] A) {
    int[] B = new int[A.length];

    if (A == null || A.length < 1)
        return B;

    B[0] = 1;
    int temp = 1;

    for (int i = 1; i <= A.length - 1; i++)
        B[i] = A[i-1] * B[i-1];

    for (int i = A.length - 2; i >= 0; i--) {
        temp *= A[i+1];
        B[i] *= temp;
    }

    return B;
}