Leetcode之Product of Array Except Self 问题
问题描述:
Given an array of n integers where n > 1, nums
, return an arrayoutput
such thatoutput[i]
is equal to the product of all the elements ofnums
exceptnums[i]
.
Solve it without division and in O(n).
示例:
For example, given [1,2,3,4]
, return [24,12,8,6]
.
1对应的是2*3*4=24;
2对应的是1*3*4=12;
3对应的是1*2*4=8;
4对应的是1*2*3=6
问题来源:Product of Array Self (详细地址:https://leetcode.com/problems/product-of-array-except-self/description/)
思路分析:刚开始你可能会想到把所有元素乘起来,然后分别除以每个元素的话,不就得到结果了吗?但是题目规定了咱们不能用除法来解决战斗,所以只能寻找别的方法了。我们可以用两个数组分别得到该元素左边所有相乘的结果和右边所有元素的乘积,最后把这两个结果乘起来就得到最终该元素的乘积结果了啊。
下面举个例子讲讲:
nums: 2 3 4 5
left[]: 1 2 2*3 2*3*4
right[]: 3*4*5 4*5 5 1
我相信把这个图列举出来,应该没有看不懂的同学了吧,最后,咱们在这为了节省数组的开销,我们就直接采用left和right,而不用数组来了,只是最终结果必须得用数组保存起来。
left的表达式是:i从左往右,left *= nums[i - 1],然后将每一个left存到对应的result中;
right的表达式是:j从右往左,right *= nums[j + 1],然后将得到的每一个right和其对应的result乘起来得到最终的结果,放到对应的result数组中。
代码: