您现在的位置是:首页 >其他 >图解LeetCode——238. 除自身以外数组的乘积网站首页其他
图解LeetCode——238. 除自身以外数组的乘积
一、题目
给你一个整数数组 nums
,返回 数组 answer
,其中 answer[i]
等于 nums
中除 nums[i]
之外其余各元素的乘积 。
题目数据 保证 数组 nums
之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。
请不要使用除法,且在 O(n)
时间复杂度内完成此题。
二、示例
2.1> 示例 1:
【输入】 nums = [1,2,3,4]
【输出】 [24,12,8,6]
2.2> 示例 2:
【输入】 nums = [-1,1,0,-3,3]
【输出】 [0,0,9,0,0]
提示:
2
<= nums.length <=10^5
-30
<= nums[i] <=30
- 保证 数组
nums
之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内
三、解题思路
根据题目要求,我们需要计算出数组nums
中,每个元素除自己之外的乘积值,即假设nums
包含4
个元素,分别为nums[0]
~`nums[3]`,那么最终结果如下所示:
nums[0] =
nums[1]
*nums[2]
*nums[3]
;
nums[1] =nums[0]
*nums[2]
*nums[3]
;
nums[2] =nums[0]
*nums[1]
*nums[3]
;
nums[3] =nums[0]
*nums[1]
*nums[2]
;
但是如果按照上面计算我们会发现一个问题,就是会出现很多重复计算,比如我们计算nums[0]
和nums[1]
的时候,针对nums[2]
* nums[3]
这部分就是重复计算的。所以,为了解决这个问题,我们可以看下面这个图,在这个图中白色的格子
表示不参与计算,那么正好可以分割为左下角和右上角两部分数字集合,具体情况请见下图所述:
针对上面的分析,我们可以分为两部分对数组nums
进行计算操作:
【正向遍历数组】 这种遍历方式,我们可以来计算左下角的数字乘积;
【逆向遍历数组】 这种遍历方式,我们可以来计算右上角的数字乘积(用temp保存),然后与左下角再执行相乘操作;
好了,如上就是本题的解题思路了,为了便于大家理解,我们以nums = [1,2,3,4]
为例,看一下具体的操作过程。请见下图所示:
四、代码实现
class Solution {
public int[] productExceptSelf(int[] nums) {
int n = nums.length, temp = 1;
int[] result = new int[n];
result[0] = 1;
for (int i = 1; i < n; i++)
result[i] = result[i-1] * nums[i-1];
for (int i = n - 2; i >= 0; i--) {
result[i] *= temp * nums[i+1];
temp *= nums[i+1];
}
return result;
}
}
今天的文章内容就这些了:
写作不易,笔者几个小时甚至数天完成的一篇文章,只愿换来您几秒钟的 点赞 & 分享 。
更多技术干货,欢迎大家关注公众号“爪哇缪斯” ~ (^o^)/ ~ 「干货分享,每天更新」