10-24 LeetCode 238. Product of Array Except Self
Description
Given an array of n integers where n > 1, nums, return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].
Solve it without division and in O(n).
For example, given [1,2,3,4], return [24,12,8,6].
Follow up:
Could you solve it with constant space complexity? (Note: The output array does not count as extra space for the purpose of space complexity analysis.)
提供一个包含n个数的数组nums，返回一个数组output, 其中output[i]等于nums中除了第i个数以外其他所有数的乘积。
在O(n)时间复杂度内解决这个问题，并且不使用除法。
Example：
提供：
[1, 2, 3, 4]
返回：
[24, 12, 8, 6]
挑战：
用常数的额外空间完成这题，output不算额外空间。
Solution 1:
这题我没有做出来。参考了别人的答案后，发现是我数学不过关 = =！
首先我们假设nums数组为
[a1, a2, a3, a4]，
则可以得出output数组为
[a2a3a4, a1a3a4, a1a2a4, a1a2a3**]
然后发现这个数组可以由下面这两个数组的对应项相乘得到：
[1, a1, a1*a2, a1*a2*a3]
[a2*a3*a4, a3*a4, a4, 1]
于是我们就构造这样的两个数组
代码：
class Solution(object):
def productExceptSelf(self, nums):
"""
:type nums: List[int]
:rtype: List[int]
"""
array1, array2 = [], []
array1.append(1)
for i in range(1, len(nums)):
array1.append(array1[i-1] * nums[i-1])
array2.append(1)
nums = nums[::-1]
for i in range(1, len(nums)):
array2.append(array2[i-1] * nums[i-1])
array2 = array2[::-1]
for i in range(len(array2)):
array1[i] *= array2[i]
return array1
Solution2:
上面的方法虽然满足了时间复杂度为O(n),但是空间复杂度由于多用了array2而不是常数。所以这个方法对上面方法的一个优化。这个方法用一个变量num记录原本的array2数组，使额外空间变成常量1.
代码：
class Solution(object):
def productExceptSelf(self, nums):
"""
:type nums: List[int]
:rtype: List[int]
"""
array1, num = [], 1
array1.append(1)
for i in range(1, len(nums)):
array1.append(array1[i-1] * nums[i-1])
for i in list(range(0, len(nums)-1))[::-1]:
num *= nums[i+1]
array1[i] *= num
return array1
感想
做这件事有点耗时啊！
