[Leetcode] 238. Product of Array Except Self

2023/11/30閱讀時間約 4 分鐘

題目 : 238. Product of Array Except Self Medium

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:

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

Example 2:

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


# 不能用除法 時間限制O(n)

# nums = [1, 2, 3, 4]

# answer = [24,12, 8, 6]

# 24 = 2 * 3 * 4 left = 1 reght = 2*3*4

# 12 = 1 * * 3 * 4 left = 1 reght = 3*4

# 8 = 1 * 2 * 4 left = 1*2 reght = 4

# 6 = 1 * 2 * 3 left = 1*2*3 reght = 1

# left = [1,1,2,6] ->

# right = [24,12,4,1] <-

# answer = left*right = [24,12,8,6]

class Solution:
def productExceptSelf(self, nums: List[int]) -> List[int]:


length = len(nums)

L, R, answer = [0]*length, [0]*length, [0]*length

L[0] = 1
for i in range(1, length):
L[i] = nums[i-1] * L[i-1]

R[length-1] = 1
for i in range(length-2, -1, -1):
R[i] = R[i+1] * nums[i+1]

for i in range(length):
answer[i] = R[i] * L[i]

return answer


  1. 只使用1個陣列存取

line 7 : 因為第1個元素的左邊沒有值可以相乘,所以直接assign 1給它

line 8 : 先將左邊的部分存到anwer陣列中

line 11 : buff是暫存右邊乘積的數值,倒數第1個元素的右邊沒有值,所以assign 1 給它

line 12 : 設1個for迴圈,從倒數第2個元素開始做計算,將原先存在answer的左邊乘積乘上buff(右邊乘積),即可得出最後的答案

class Solution:
def productExceptSelf(self, nums: List[int]) -> List[int]:

length = len(nums)

answer = [0]*length
answer[0] = 1
for i in range(1,length):
answer[i] = answer[i-1] * nums[i-1]

buff = 1
for i in range(length-2, -1, -1):
buff *= nums[i+1]
answer[i] *= buff

return answer






7會員
36內容數
這裡會放一些我寫過的 Leetcode 解題和學習新技術的筆記
留言0
查看全部
發表第一個留言支持創作者!