0238. Product of Array Except Self (Medium)

Question

Given an array nums of n integers where n > 1, return an array outputsuch that output[i] is equal to the product of all the elements of numsexcept nums[i].

Example:

1
2

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

Note: Please solve it ** without division** and in O(n).

Follow up:
Could you solve it with constant space complexity? (The output array does not count as extra space for the purpose of space complexity analysis.)

分析/解題

題目給定一個陣列nums，目標是產生一個output陣列，
這個output上的output[i]都相當於除了nums[i]以外其他的乘積。
要求不能用除法且必須在O(n)的時間完成。
延伸要求：用來做為輸出的output不算在額外的空間內的話，
是否可使用常數空間複雜度來解決此題？(即僅使用O(1)空間)

這題如果用暴力法來解的話，
就是使用兩層for-loop，將每個output[i]先初始化為1，
再進行對其他值的相乘(也就是要乘N-1次)，
所需的總乘法會是N*(N-1)，故時間複雜度為O(N²)。

這樣顯然速度不太好，我們再來考慮一下實際的情形。

1
2
3
4

nums  2     3     4     5
res   3*4*5 2*4*5 2*3*5 2*3*4
l           2     2*3   2*3*4
r     3*4*5 4*5   5

假設有一個陣列是[2, 3, 4, 5]，而我們要求的結果是res，
按照定義我們可以先將res的結果寫出。
仔細觀察我們可以發現，如果將res的每項拆成兩組相乘 ，
我們可以拆分成l, r兩個陣列，
當中l從index 1 開始往後推 有數值，依序是2, 2*3, 2*3*4 。
r則從index 2 開始往回推 有數值，依序是5, 4*5, 3*4*5 。

(這邊的拆分就是取明顯有斷層 的部分，空出來的部分為1 )

所以我們可以先將res初始化，用它承載l 的部分，
再依次將r從1開始，把5,4,3依序乘上去一個值以後依序乘到res中，
這樣一來計算res的時候就只有分別經歷過兩次O(N)，
時間複雜度會維持在O(N)。
同時，因為前面第一次利用了res來儲存l的部分，
第二次只用單個變數r來依序記錄要乘的順序，
故扣除res以後空間複雜度為O(1)。

Java

Python

面試實際可能會遇到的問題

「時間/空間複雜度？」
(O(N)/O(1))

相似及延伸

Special Thanks suggestions/corrections from viewers:
(歡迎提供意見協助更正歐~)

從LeetCode學演算法，我們下次見囉，掰~