238. Product of Array Except Self

Question: Product of Array Except Self

Solution1

1. 先製作 prefix & postfix list
   • prefix: prefix[i] = nums[0] * nums[1] * nums[2] * … * nums[i]
   • postfix: postfix[i] = nums[-1] * nums[-2] * nums[-3] * … * nums[i]
2. 計算答案:
   • ans[i] = prefix[i - 1] * postfix[i + 1]

舉例：

如下圖，nums[2] 為 3

• ans[2] = prefix[1] * postfix[3]
• prefix[1] = nums[0] * nums[1] = 1 * 2 = 2
• postfix[3] = nums[3] = 4
• ans[2] = 2 * 4 = 8

Time Complexity: O(n)

Space: O(n)

有沒有辦法讓空間複雜度只有 O(1)：不要存 prefix, postfix，直接存入答案！

Solution2

1. 邊計算 prefix 邊存入 ans

2. 爾後計算 postfix 後，取出 ans 值，乘上 postfix 再存回去

3. 處理頭尾

• 頭只會有 postfix:
  • ans[0] = 1 * postfix[1]
  • 所以最一開始的 prefix 要設成 1，放入 ans[0] 中，再將 prefix * nums[0] （見 code）
• 尾只會有 prefix:
  • ans[-1] = prefix[-2] * 1
  • 所以最一開始的 postfix 要設成 1，放入 ans[-1] 中，再將 postfix * nums[-1] （見 code）

Time Complexity: O(n)

Space Complexity: O(1)

class Solution:

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

nums_len = len(nums)

ans = [1] * nums_len

pre_multiple, post_multiple = 1, 1 # 最一開始的 prefix, postfix 設成 1

for i in range(nums_len):

ans[i] = pre_multiple # 將 prefix 先放入 ans 再乘

pre_multiple *= nums[i]

for i in range(nums_len - 1, -1, -1):

ans[i] *= post_multiple # 將 postfix 先放入 ans 再乘

post_multiple *= nums[i]

return ans

Solution3

如果可以用除法的話，就把所有數字乘起來的總和，除以該數字本身。

Video Solution