构建乘积数组

http://www.nowcoder.com/questionTerminal/94a4d381a68b47b7a8bed86f2975db46

题目的主要信息：

给定一个数组A，要求返回数组B，数组B每个元素等于数组A所有元素除了对应下标以外的全部元素的乘积
即 $B [i] = A [0] * A [1] * . . . * A [i - 1] * A [i + 1] * . . . * A [n - 1]$
程序不能使用除法

举一反三：

学习完本题的思路你可以解决如下题目：

JZ17. 打印从1到最大的n位数

JZ64. 求1+2+3+...+n

方法：双向遍历（推荐使用）

思路：

alt

如上图所示，矩阵中由对角线1将其分成了上三角和下三角。我们先看下三角，如果我们累乘的时候，B[1]是在B[0]的基础上乘了新增的一个A[0]，B[2]是在B[1]的基础上乘了新增的一个A[1]，那我们可以遍历数组的过程中不断将数组B的前一个数与数组A的前一个数相乘就得到了下三角中数组B的当前数。同理啊，我们在上三角中，用一个变量存储从右到左的累乘，每次只会多乘上一个数字。这样，两次遍历就可以解决。

具体做法：

step 1：初始化数组B，第一个元素为1.
step 2：从左到右遍历数组A，将数组B的前一个数与数组A的前一个数相乘就得到了下三角中数组B的当前数。
step 3：再从右到左遍历数组A，用一个数字记录从右到左上三角中的累乘，每次只会乘上一个数，同时给数组B对应部分也乘上该累乘。

图示：

alt

Java实现代码：

import java.util.ArrayList;
public class Solution {
    public int[] multiply(int[] A) {
        //初始化数组B
        int[] B = new int[A.length];
        B[0] = 1;
        //先乘左边，从左到右
        for(int i = 1; i < A.length; i++)
            //每多一位由数组B左边的元素多乘一个前面A的元素
            B[i] = B[i - 1] * A[i - 1];
        int temp = 1;
        //再乘右边，从右到左
        for(int i = A.length - 1; i >= 0; i--){
            //temp为右边的累乘
            B[i] *= temp;
            temp *= A[i];
        }
        return B;
    }
}

C++实现代码：

class Solution {
public:
    vector<int> multiply(const vector<int>& A) {
        //初始化数组B
        vector<int> B(A.size(), 1);
        //先乘左边，从左到右
        for(int i = 1; i < A.size(); i++)
            //每多一位由数组B左边的元素多乘一个前面A的元素
            B[i] = B[i - 1] * A[i - 1];
        int temp = 1;
        //再乘右边，从右到左
        for(int i = A.size() - 1; i >= 0; i--){
            //temp为右边的累乘
            B[i] *= temp;
            temp *= A[i];
        }
        return B;
    }
};

Python实现代码：

class Solution:
    def multiply(self , A: List[int]) -> List[int]:
        #初始化数组B
        B = [1 for i in range(len(A))]
        #先乘左边，从左到右
        for i in range(1, len(A)):
            #每多一位由数组B左边的元素多乘一个前面A的元素
            B[i] = B[i - 1] * A[i - 1]
        temp = 1
        #再乘右边，从右到左
        for i in reversed(range(len(A))):
            #temp为右边的累乘
            B[i] *= temp
            temp *= A[i]
        return B

复杂度分析：