題目 : 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].
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個陣列存取
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
