构建乘积数组

---

题目描述

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

解题思路

本题的目的，就是求出不包含第i个元素，其余元素之积，构成新的数组B。

通过一个例子来说明：

数组A={1,2,3,4,5}, 数组B为上图中，每行除去绿色块其余部分的乘积。通过观察可知，每行的乘积都可分为两部分，即（黄色部分之积） * （粉色部分之积）定义粉色部分之积为C[i],黄色部分之积为D[i].

通过图分析可知，粉色部分C[i] = C[i - 1] * A[i - 1]，黄色部分D[i] = D[i + 1] * A[i + 1]

可以先求出粉色部分的积，和黄色部分的积，然后求出数组B。

代码

class Solution
{
public:
    vector<int> multiply (const vector<int> &A)
    {
        int n = A.size();
        vector<int> B(n);
        if (n <= 0)
            return B;
        // 先把粉色部分之积存放在B中
        B[0] = 1;
        for (int i = 1; i < n; i++)
        {
            B[i] = B[i - 1] * A[i - 1]; // 粉色部分， 第 i 行的积。
        }
        
        // 计算黄色部分的积，并求出B
        int temp = 1;
        for (int i = n - 2; i >= 0; i--)
        {
            temp *= A[i + 1]; // 黄色部分，第 i 行的积
            B[i] *= temp; // 数组B，第 i 行的积
        }
        return B;
    }
};

参考博文链接：https://cuijiahua.com/blog/2018/01/basis_51.html