构建乘积数组

题目的主要信息：

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

举一反三：

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

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

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

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

思路：

如上图所示，矩阵中由对角线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对应部分也乘上该累乘。

图示：

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

复杂度分析：

• 时间复杂度：$O(n)O(n)$，其中$nn$为数组A的长度，遍历两次数组
• 空间复杂度：$O(1)O(1)$，数组B为返回必要空间，不属于额外空间