AcWing 86. 构建乘积数组
原题链接
中等
作者:
adamXu
,
2020-10-12 12:17:28
,
所有人可见
,
阅读 522
class Solution {
public:
vector<int> multiply(const vector<int>& A) {
//优化的解法,我们将B[i] 分为两个部分 1.A[1]-A[i - 1] 即左边的部分 2.A[i + 1]-A[n]
//即右边的部分,用一重循环分别计算左右边再相乘即答案,对应时间复杂度为On,空间O1
if(A.empty()) return vector<int>();
int n = A.size();
vector<int> B(n);
for(int i = 0,p = 1;i < n;++i){
B[i] = p;
p *= A[i];
}
for(int i = n - 1,p = 1;i >= 0;i--){
B[i] *= p;
p *= A[i];
}
return B;
/*
//常规解法,两重循环来做,时间复杂度O(n^2),空间O(1)
int n = A.size();
vector<int> B(n,1);
for(int i = 0;i < n;i++)
for(int j = 0;j < n;++j){
if(i == j) continue;
B[i] *= A[j];
}
return B;*/
}
};