构建乘积数组

51. 构建乘积数组

题目描述

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

解题思路：

• 思路1: 遍历数组，时间复杂度O(n)
• 思路2:

Bi	A0	A1	A2	…	An-2	An-1
B0	1	A1	A2	…	An-2	An-1
B1	A0	1	A2	…	An-2	An-1
B2	A0	A1	1	…	An-2	An-1
B0	…	…	…	…	…	…
Bn-2	A0	A1	A2	…	1	An-1
Bn-1	A0	A1	A2	…	An-2	1

通过观察，B_i的值可以看作表格中每一行的乘积，下三角连乘易求得，上三角，从下向上也是连乘，所以我们可以先计算下三角中的连乘，再算上三角的连乘，将B_i两部分相乘即可。

解答：

// 解法1:
class Solution {
public:
    vector<int> multiply(const vector<int>& A) {
        int len = A.size();
        vector<int> B;
        for(int i = 0; i < len; ++i)
        {
            int bi = 1;
            for(int j = 0; j < len; ++j)
            {
                if(i == j)
                    continue;
                bi *= A[j]; 
            }
            B.push_back(bi);
        }
        return B;
    }
};

// 解法2:
class Solution {
public:
    vector<int> multiply(const vector<int>& A) {
        int len = A.size();
        vector<int> B(len);
        if(len <= 0)
            return B;
        B[0] = 1;
        // 计算下三角
        for(int i = 1; i < len; ++i)
        {
            B[i] = B[i-1] * A[i-1];
        }
        int tmp = 1;
        //计算上三角
        for(int i = len - 2; i >= 0; --i)
        {
            tmp *= A[i+1];
            B[i] *= tmp;
        }
        return B;
    }
};