题目描述
给你一个整数数组 nums,返回 数组 answer ,其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。
题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。
请 不要使用除法,且在 O(n) 时间复杂度内完成此题。
样例
输入: nums = [1,2,3,4]
输出: [24,12,8,6]
输入: nums = [-1,1,0,-3,3]
输出: [0,0,9,0,0]
算法1
前后缀分解:
-
通过递推预处理出前缀的乘积,后缀也可以递推出来,也是O(n)的。
前缀的处理: p[i] = a0 * a1 * a2 … ai-1 ,即p[i] = p[i-1] * ai-1
后缀的处理: S[i] = an-1 * an-2 … ai+1 -
此时 答案数组 = 前缀 * 后缀
结果数组表示为 bi = pi * si ,该式子的意思为:乘积 = a[i]的前缀乘积 * a[i]的后缀乘积 -
如何做到只开一个数组?先开一个前缀数组,并把前缀预处理出来,计算后缀的时候不能再开新数组,对于后缀的计算,我们使用一个变量来存(从后往前计算)。
-
如何将前缀数组和答案数组合并为一个数组呢?计算答案时,由p[i] = p[i] * s ,左边的p表示答案,右边p表示前缀,s表示后缀,该表达式从size-1向前遍历(即从后向前遍历),因为此时后缀还未计算,在计算后缀的同时实现计算答案。计算后缀需要从后往前,而前缀我们在之前已经处理出来了,因此从后往前遍历,计算后缀的同时,也能计算答案。
-
但b和p是两个数组,题目要求只开一个数组,因此在处理后缀的同时,将前缀数组不断覆盖为结果数组
时间复杂度
-
处理出前缀乘积,需要O(n),处理后缀乘积,也需要O(n),因此时间复杂度为O(n)。
-
空间复杂度为O(1),输出的结果数组不被视为额外空间,我们在计算出前缀数组后,将前缀数组覆盖为结果数组了,因此额外消耗空间为O(1)
C++ 代码
class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {
// 预处理前缀乘积
// 注意:第一个元素的前缀乘积需要设置为1,虽然它本应该没有前缀乘积,但计算结果时,需要乘上后缀乘积,所以不能将前缀乘积设置为0
vector<int>pre(nums.size(),1);
for(int i=1;i<nums.size();i++)
{
pre[i]=pre[i-1]*nums[i-1];
}
// 处理后缀的同时处理结果
int s=1;
for(int i=nums.size()-1;i>=0;i--)
{
pre[i]=pre[i]*s;
s*=nums[i];
}
return pre;
}
};
算法2
blablabla
时间复杂度
参考文献
C++ 代码
blablabla