前后缀分解
观察式子不难发现:
B[i]
是 A[0 ~ i - 1]
和A[(i + 1) ~ (n - 1)]
的乘积
分别是A[]
的前缀和后缀的乘积,因此考虑前后缀分解
可以用两个变量prefix
和suffix
初始的时候prefix = 1, suffix = A[0] * A[1] * ... * A[n - 1]
顺序枚举所有A[]
中所有元素,每一次先将suffix
除去当前元素A[i]
,然后B[i]
的值为:prefix * suffix
,随后把A[i]
加入prefix
这样操作使得一次顺序枚举就可以计算完B[]
的所有值,且满足题目要求:A[]
的前缀和后缀的乘积 ( 但是需要注意除 $0$ 的情况,且 $0$ 一多时间复杂度就会退化为:$\mathcal O(n^2)$ )
或是用两次遍历:顺序和逆序
依次累乘上A[]
的前缀和后缀的乘积
时间复杂度:$\mathcal O(n)$
用除法 [ 一次遍历 ]
做除法需要注意 $\div 0$ 的情况
class Solution {
public:
vector<int> multiply(const vector<int>& A) {
int p = 1, s = 1; // 1 作为基数
int n = A.size();
vector<int> res(n);
for (auto x : A)
s *= x;
for (int i = 0; i < n; i ++ )
{
if (!A[i]) // A[i] == 0 // 注意特判!
{
s = 1;
for (int j = i + 1; j < n; j ++ )
s *= A[j];
}
else s /= A[i]; // 每一次进入先把对应的 A[i] 除掉
res[i] = s * p;
p *= A[i];
}
return res;
}
};
不用除法 [ 两次遍历 ]
class Solution {
public:
vector<int> multiply(const vector<int>& A) {
int t = 1, n = A.size();
vector<int> res(n);
for (int i = 0; i < n; i ++ )
{
res[i] = t;
t *= A[i];
}
t = 1;
for (int i = n - 1; i >= 0; i -- )
{
res[i] *= t;
t *= A[i];
}
return res;
}
};