AcWing 86. 构建乘积数组
原题链接
中等
作者:
二十七杯酒
,
2021-01-01 15:31:29
,
所有人可见
,
阅读 304
3次遍历
class Solution {
public:
vector<int> constructArr(vector<int>& a) {
if(a.size() <= 1)return a;
vector<int> left_multi;
vector<int> right_multi;
int len = a.size();
int temp = 1;
for(int i = 0; i < len; i ++){
temp *= a[i];
left_multi.push_back(temp);
}
temp = 1;
for(int i = len - 1; i >= 0; i -- ){
temp *= a[i];
right_multi.push_back(temp);
}
vector<int> res;
for(int i = 0; i < len; i ++ ){
int left, right;
if(i - 1 < 0)left = 1;
else left = left_multi[i - 1];
if(i + 1 >= len)right = 1;
else right = right_multi[len - 1 - (i + 1)];
res.push_back(left * right);
}
return res;
}
};
1次遍历
class Solution {
public:
vector<int> constructArr(vector<int>& a) {
int len = a.size();
vector<int> b(len, 1);
if(len == 0) return b;
int left = 1, right = 1;
for(int i = 0; i < len; i++){
b[i] *= left;
left *= a[i]; // 持有左边的所有数的乘积
b[len - i - 1] *= right;
right *= a[len -i - 1]; // 持有右边的所有数的乘积
}
return b;
}
};