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的值可以看作表格中每一行的乘積姨伟，下三角連乘易求得惩琉，上三角，從下向上也是連乘夺荒，所以我們可以先計(jì)算下三角中的連乘瞒渠，再算上三角的連乘良蒸，將Bi兩部分相乘即可。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
解答：
// 解法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)壁紙
