起公司名称大全免费网站,深圳建网站服务商,做一个自己的免费网站,html网页制作app下载1. 题目解析
题目链接#xff1a;238. 除自身以外数组的乘积 这个问题的理解其实相当简单#xff0c;只需看一下示例#xff0c;基本就能明白其含义了。
核心在于计算题目所给数组除本身外其他元素的积的数组返回即可。
2. 算法原理
为了计算每个位置i的最终结果ret[i]238. 除自身以外数组的乘积 这个问题的理解其实相当简单只需看一下示例基本就能明白其含义了。
核心在于计算题目所给数组除本身外其他元素的积的数组返回即可。
2. 算法原理
为了计算每个位置i的最终结果ret[i]我们需要考虑两部分
nums[0] * nums[1] * nums[2] * ... * nums[i - 1]表示位置i之前的所有元素的乘积。nums[i 1] * nums[i 2] * ... * nums[n - 1]表示位置i之后的所有元素的乘积。
为了高效计算我们可以利用前缀和的概念构建两个辅助数组post和suf。
post数组存储每个位置i之前的所有元素的乘积即[0, i - 1]区间内元素的累积乘积。suf数组存储每个位置i之后的所有元素的乘积即[i 1, n - 1]区间内元素的累积乘积。
通过预先计算post和suf数组我们可以快速得到每个位置i的最终结果ret[i]即ret[i] post[i] * suf[i]。这样我们就能够高效地处理所有位置的结果。
3. 代码编写
class Solution {
public:vectorint productExceptSelf(vectorint nums) {int n nums.size();vectorint f(n), g(n);f[0] g[n - 1] 1;for(int i 1; i n; i)f[i] f[i - 1] * nums[i - 1];for(int i n - 2; i 0; i--)g[i] g[i 1] * nums[i 1];vectorint ret(n);for(int i 0; i n; i)ret[i] f[i] * g[i];return ret;}
};
The Last
嗯就是这样啦文章到这里就结束啦真心感谢你花时间来读。
觉得有点收获的话不妨给我点个赞吧
如果发现文章有啥漏洞或错误的地方欢迎私信我或者在评论里提醒一声~
