Lunski's Clutter

This is a place to put my clutters, no matter you like it or not, welcome here.

0%

238. Product of Array Except Self

Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i].

The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

You must write an algorithm that runs in O(n) time and without using the division operation.

Example 1:

1
2
Input: nums = [1,2,3,4]
Output: [24,12,8,6]

Example 2:

1
2
Input: nums = [-1,1,0,-3,3]
Output: [0,0,9,0,0]

題目不能用除法,只要先算出向右跟向左2個array相乘即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
T:O(n), S:O(n)
class Solution(object):
def productExceptSelf(self, nums):
"""
:type nums: List[int]
:rtype: List[int]
"""
n = len(nums)
temp = 1
res = [0 for i in range(n)]
res[0] = 1
for i in range(1, n):
res[i] = res[i-1]*nums[i-1]
for i in range(n-2,-1,-1):
temp*=nums[i+1]
res[i] *=temp
return res

ref


如果你覺得這篇文章很棒,請你不吝點讚 (゚∀゚)

Welcome to my other publishing channels