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.)
class Solution(object):
def productExceptSelf(self, nums):
"""
:type nums: List[int]
:rtype: List[int]
"""
nums_length = len(nums)
forward, backward = [1], [1]
for i in range(nums_length):
forward.append(nums[i] * forward[i])
backward.append(nums[-(i+1)] * backward[i])
return [forward[x]*backward[-(x+2)] for x in range(nums_length)]
Show me the code 2
一个更通俗易懂的写法：
class Solution(object):
def productExceptSelf(self, nums):
"""
:type nums: List[int]
:rtype: List[int]
"""
nums.insert(0, 1)
nums.append(1)
left, right, result = [1], [1], []
for i in nums[1:-1]:
left.append(left[-1] * i)
for i in nums[-2:0:-1]:
right.append(right[-1] * i)
right.reverse()
for i in range(len(nums) - 2):
result.append(left[i] * right[i+1])
return result
238. Product of Array Except Self
tags: 印象笔记
[toc]
Question
Follow up
Solution
值 = 所有左侧的数的乘积 所有右侧的数的乘积 可以用两个列表表示所有左侧数的乘积与右侧数的乘积。 给定数组[1, 2, 3, 4] forward = [1, 1, 2, 6, 24] backward = [1, 4, 12, 24, 24] 值 = forward[i] backward[-(i+2)]
Show me the code 1
Show me the code 2
一个更通俗易懂的写法：
- 完 -