Leetcode 238. Product of Array Except Self

文章作者:Tyan
博客:noahsnail.com  |  CSDN  |  简书

1. Description

Product of Array Except Self

2. Solution

解析:可以使用两个数组left, right分别保存从左边到第i个元素的积以及从右边到第i个元素的积,则结果中result[i]=left[i-1] * right[i+1],这种情况下的空间复杂度为O(n)。另一种方式是,计算左边元素积的同时更新结果数组,计算右边积的同时也更新结果数组,这种情况下的空间复杂度为O(1)

  • Version 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
def productExceptSelf(self, nums):
length = len(nums)
result = [1] * length
left = [1] * length
right = [1] * length
left[0] = nums[0]
right[-1] = nums[-1]
for i in range(length):
if i > 0:
left[i] = left[i - 1] * nums[i]
if i < length - 1:
right[-i - 2] = nums[-i - 2] * right[-i - 1]
for i in range(length):
if i == 0:
result[i] = right[i + 1]
elif i == length - 1:
result[i] = left[i - 1]
else:
result[i] = left[i - 1] * right[i + 1]
return result
  • Version 2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
def productExceptSelf(self, nums):
length = len(nums)
result = [1] * length
left = 1
right = 1
for i in range(length - 1):
left *= nums[i]
result[i + 1] = result[i + 1] * left
for i in range(length - 1, 0, -1):
right *= nums[i]
result[i - 1] = result[i - 1] * right
return result

Reference

  1. https://leetcode.com/problems/product-of-array-except-self/
如果有收获,可以请我喝杯咖啡!