什么是网络营销网络营销的目的有哪些内容,wordpress的seo如何写关键词,asp.net 网站管理工具 安全,有自己域名如何做网站一. 题目描述
原题链接
给你一个整数数组 nums#xff0c;返回 数组 answer #xff0c;其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。
题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。
请 不要使用除法…一. 题目描述
原题链接
给你一个整数数组 nums返回 数组 answer 其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。
题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。
请 不要使用除法且在 O(n) 时间复杂度内完成此题。 示例 1:
输入: nums [1,2,3,4]
输出: [24,12,8,6]示例 2:
输入: nums [-1,1,0,-3,3]
输出: [0,0,9,0,0]提示
2 nums.length 105-30 nums[i] 30保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内
二. 解题思路
本题意思是计算每一个nums[i]的值其中nums[i] 的值为除自身以外的其他值的乘积。
首先我们定义两个数组 left 和 right 其中 left 数组用来计算数组的前缀和right 数组用来计算数组的后缀和至于最终计算结果我们只需要在原数组上操作即可省略了空间的浪费nums[i] 的最终结果就等于nums[i - 1] 的前缀和乘 nums[i 1] 的后缀和即 nums[i] left[i - 1] * right[i 1]。
但是在计算nums[0] 和nums[n - 1] 的时候我们发现会出现数组越界错误所以我们将 left 数组元素统一后移一位然后将 left[0] 赋予 1将 right 数组扩展一位right[n] 赋予1 。所以就可以得出nums[i] left[i] * right[i 1] (原本是 left[i - 1] * right[i 1]但是 left 元素统一后移一位所以下标也会移动但是 right 数组只是扩展对下标未改动)
运算过程如图所示 三. 代码
class Solution {
public:vectorint productExceptSelf(vectorint nums) {int n nums.size();int sum 0;vectorint left(n 1);vectorint right(n 1);left[0] 1;right[n] 1;for(int i 0; i n; i){left[i 1] nums[i] * left[i];}for(int i n - 1; i 0; i--){right[i] right[i 1] * nums[i];}for(int i 0; i n; i){nums[i] left[i] * right[i 1];}return nums;}
};
四. 总结
本题属于前缀和和后缀和的集合考察属于中等题目大家可以练习一下但是一定要考虑在左右位置计算的时候的越界问题。
时间复杂度O(n)
空间复杂度O(n)
爱思考的小伙伴可以想一下本题如何用O(1)的空间复杂度实现欢迎评论
喜欢的话给个关注吧
