【C++算法】28.前缀和_除自身以外数组的乘积
文章目录
- 题目链接:
- 题目描述:
- 解法
- C++ 算法代码:
- 图解
题目链接:
238. 除自身以外数组的乘积
题目描述:
解法
暴力枚举:O(n2)
边枚举位置,边算乘积。
前缀和思想:
- 预处理前缀积和后缀积
f
:前缀积
数组 这里面f[i]
表示:[0,i-1]
区间所有元素的积
g
:后缀积
数组 这里面g[i]
表示:[i+1,n-1]
区间所有元素的积
f[i]=f[i-1]*nums[i-1]
g[i]=g[i+1]*nums[i+1]
-
使用
ret
数组存储i
,使得i=f[i]*g[i]
-
注意细节问题,比如
i=0
的时候i-1
不存在以及
f[0]
要设置为1
,g[n-1]
设置为1
因为如果
f[0]=0
,那么f[1]=0*nums[0]=0
,后面就全0
了
C++ 算法代码:
class Solution
{
public:
vector<int> productExceptSelf(vector<int>& nums)
{
// lprod 表示:[0, i - 1] 区间内所有元素的乘积
// rprod 表示:[i + 1, n - 1] 区间内所有元素的乘积
int n = nums.size();
vector<int> lprod(n + 1), rprod(n + 1);
lprod[0] = 1, rprod[n - 1] = 1;
// 预处理前缀积以及后缀积
for(int i = 1; i < n; i++)
lprod[i] = lprod[i - 1] * nums[i - 1];
for(int i = n - 2; i >= 0; i--)
rprod[i] = rprod[i + 1] * nums[i + 1];
// 处理结果数组
vector<int> ret(n);
for(int i = 0; i < n; i++)
ret[i] = lprod[i] * rprod[i];
return ret;
}
};
图解
例如:nums = [1,2,3,4]