构建乘积数组

来源：https://www.nowcoder.com/questionTerminal/94a4d381a68b47b7a8bed86f2975db46

给定一个数组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]。不能使用除法。

第一个for循环，求出B[i]中A[0]_{A[i-1]的乘积，第二个for循环，求出A[i+1]}A[n-1]的乘积，并将两部分乘积相乘。

Java

public class Solution {
    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];
        }
        int temp = 1;
        for(int i=B.length-2; i>-1; i--) {
            temp *= A[i+1];
            B[i] *= temp;
        }
        return B;
    }
}

Python

class Solution:
    def multiply(self, A):
        if not A:
            return A
        n = len(A)
        B = [1] * n
        for i in range(n-1):
            B[i+1] = B[i] * A[i]
        tmp = 1
        for i in range(n-1, 0, -1):
            tmp *= A[i]
            B[i-1] *= tmp
        return B