51. 構(gòu)建乘積數(shù)組

題目描述

給定一個(gè)數(shù)組A[0,1,...,n-1],請(qǐng)構(gòu)建一個(gè)數(shù)組B[0,1,...,n-1],其中B中的元素B[i]=A[0]*A[1]*...*A[i-1]*A[i+1]*...*A[n-1]。不能使用除法。

解題思路：

• 思路1: 遍歷數(shù)組，時(shí)間復(fù)雜度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的值可以看作表格中每一行的乘積，下三角連乘易求得，上三角，從下向上也是連乘，所以我們可以先計(jì)算下三角中的連乘，再算上三角的連乘，將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;
        // 計(jì)算下三角
        for(int i = 1; i < len; ++i)
        {
            B[i] = B[i-1] * A[i-1];
        }
        int tmp = 1;
        //計(jì)算上三角
        for(int i = len - 2; i >= 0; --i)
        {
            tmp *= A[i+1];
            B[i] *= tmp;
        }
        return B;
    }
};

大家有興趣可以訪問我的個(gè)人博客，不定時(shí)更新一些內(nèi)容哦！

圖片來自必應(yīng)壁紙