概述
https://leetcode-cn.com/problems/gou-jian-cheng-ji-shu-zu-lcof/
不能使用除法。
暴力解
class Solution {
public:
vector<int> constructArr(vector<int>& a) {
vector<int> ans = a;
for (int i = 0; i < a.size(); i ++) {
ans[i] = 1;
for (int j = 0; j < a.size(); j ++) {
if (i != j) ans[i] *= a[j];
}
}
return ans;
}
};
O(n^2) 时间复杂度。
TLE 了。
前缀积和后缀积
O(n) 的时间复杂度。
class Solution {
public:
vector<int> constructArr(vector<int>& a) {
vector<int> pre = a;
vector<int> post = a;
for (int i = 1; i < a.size(); i ++) {
pre[i] = pre[i-1] * a[i];
}
for (int i = a.size() - 2; i >= 0; i --) {
post[i] = post[i+1] * a[i];
}
vector<int> ans = a;
for (int i = 0; i < a.size(); i ++) {
int preProduct = 1;
if (i != 0) preProduct = pre[i-1];
int postProduct = 1;
if (i != a.size() - 1) postProduct = post[i+1];
ans[i] = preProduct * postProduct;
}
return ans;
}
};