238. 除自身以外數組的乘積 （點擊查看題目）
題目描述
給定長度為 n 的整數數組 nums，其中 n > 1，返回輸出數組 output ，其中 output[i] 等於 nums 中除 nums[i] 之外其餘各元素的乘積。
示例:
說明: 請 不要使用除法，且在 O(n) 時間複雜度內完成此題。
進階：
你可以在常數空間複雜度內完成這個題目嗎？（ 出於對空間複雜度分析的目的，輸出數組 不被視為 額外空間。）
解決方案
概述
這似乎是一個簡單的問題，可以在線性時間和空間內解決。可以先計算給定數組所有元素的乘積，然後對數組中的每個元素 x ，將乘積除以 x 來求得除自身值的以外的數組乘積。
然後這樣的解決方法有一個問題，就是如果輸入數組中出現 0，那麼這個方法就失效了。而且在問題中說明了不允許使用除法運算。這增加了這個問題的難度。
方法一：左右乘積列表
我們不必將所有數字的乘積除以給定索引處的數字得到相應的答案，而是可以利用索引處左側的所有數字乘積和右側所有數字的乘積相乘得到答案。
對於給定索引 i，我們將使用它左邊所有數字的乘積乘以右邊所有數字的乘積。讓我們更加具體的描述這個算法。
算法：
- 初始化兩個空數組 L 和 R。對於給定索引 i，L[i] 代表的是 i左側所有數字的乘積，R[i] 代表的是 i 右側所有數字的乘積。
- 我們需要用兩個循環來填充 L 和 R 數組的值。對於數組 L，L[0]應該是 1，因為第一個元素的左邊沒有元素。對於其他元素：L[i]=L[i-1]*nums[i-1]。
- 同理，對於數組 R，R[length-1] 應為 1。length 指的是輸入數組的大小。其他元素：R[i]=R[i+1]*nums[i+1]。
- 當 R 和 L 數組填充完成，我們只需要在輸入數組上迭代，且索引 i處的值為：L[i]*R[i]。
讓我們用以下圖片看看算法是如何工作的：
Python 實現（請在電腦端查看代碼）
<code>class Solution: def productExceptSelf(self, nums: List[int]) -> List[int]: # The length of the input array length = len(nums) # The left and right arrays as described in the algorithm L, R, answer = [0]*length, [0]*length, [0]*length # L[i] contains the product of all the elements to the left # Note: for the element at index '0', there are no elements to the left, # so the L[0] would be 1 L[0] = 1 for i in range(1, length): # L[i - 1] already contains the product of elements to the left of 'i - 1' # Simply multiplying it with nums[i - 1] would give the product of all # elements to the left of index 'i' L[i] = nums[i - 1] * L[i - 1] # R[i] contains the product of all the elements to the right # Note: for the element at index 'length - 1', there are no elements to the right, # so the R[length - 1] would be 1 R[length - 1] = 1 for i in reversed(range(length - 1)): # R[i + 1] already contains the product of elements to the right of 'i + 1' # Simply multiplying it with nums[i + 1] would give the product of all # elements to the right of index 'i' R[i] = nums[i + 1] * R[i + 1] # Constructing the answer array for i in range(length): # For the first element, R[i] would be product except self # For the last element of the array, product except self would be L[i] # Else, multiple product of all elements to the left and to the right answer[i] = L[i] * R[i] return answer/<code>
Java 實現（請在電腦端查看代碼）
<code>class Solution { public int[] productExceptSelf(int[] nums) { // The length of the input array int length = nums.length; // The left and right arrays as described in the algorithm int[] L = new int[length]; int[] R = new int[length]; // Final answer array to be returned int[] answer = new int[length]; // L[i] contains the product of all the elements to the left // Note: for the element at index '0', there are no elements to the left, // so L[0] would be 1 L[0] = 1; for (int i = 1; i < length; i++) { // L[i - 1] already contains the product of elements to the left of 'i - 1' // Simply multiplying it with nums[i - 1] would give the product of all // elements to the left of index 'i' L[i] = nums[i - 1] * L[i - 1]; } // R[i] contains the product of all the elements to the right // Note: for the element at index 'length - 1', there are no elements to the right, // so the R[length - 1] would be 1 R[length - 1] = 1; for (int i = length - 2; i >= 0; i--) { // R[i + 1] already contains the product of elements to the right of 'i + 1' // Simply multiplying it with nums[i + 1] would give the product of all // elements to the right of index 'i' R[i] = nums[i + 1] * R[i + 1]; } // Constructing the answer array for (int i = 0; i < length; i++) { // For the first element, R[i] would be product except self // For the last element of the array, product except self would be L[i] // Else, multiple product of all elements to the left and to the right answer[i] = L[i] * R[i]; } return answer; }}/<code>複雜度分析
時間複雜度：O(N)，其中 N 指的是輸入數組的大小。
空間複雜度：O(N)，使用了 L 和 R 數組去構造答案。
方法二：空間複雜度 O(1) 的方法
儘管上面的方法已經能夠很好的解決這個問題，但是不是常數的空間複雜度。
由於輸出數組不算在空間複雜度內，那麼我們可以將 L 或 R 數組在用輸出數組來計算，然後再動態構造另一個。讓我們來看看基於這個思想的算法。
算法：
- 初始化 answer 數組，對於給定索引 i，answer[i] 代表的是 i左側所有數字的乘積。
- 構造方式與之前相同，只是我們視圖節省空間。
- 這種方法的唯一變化就是我們沒有構造 R 數組。而是用一個遍歷來跟蹤右邊元素的乘積。並更新數組 answer[i] = answer[i] * R。然後 R 更新為 R = R* nums[i]
Python 實現（請在電腦端查看代碼）
<code>class Solution: def productExceptSelf(self, nums: List[int]) -> List[int]: # The length of the input array length = len(nums) # The answer array to be returned answer = [0]*length # answer[i] contains the product of all the elements to the left # Note: for the element at index '0', there are no elements to the left, # so the answer[0] would be 1 answer[0] = 1 for i in range(1, length): # answer[i - 1] already contains the product of elements to the left of 'i - 1' # Simply multiplying it with nums[i - 1] would give the product of all # elements to the left of index 'i' answer[i] = nums[i - 1] * answer[i - 1] # R contains the product of all the elements to the right # Note: for the element at index 'length - 1', there are no elements to the right, # so the R would be 1 R = 1; for i in reversed(range(length)): # For the index 'i', R would contain the # product of all elements to the right. We update R accordingly answer[i] = answer[i] * R R *= nums[i] return answer/<code>
Java 實現（請在電腦端查看代碼）
<code>class Solution { public int[] productExceptSelf(int[] nums) { // The length of the input array int length = nums.length; // Final answer array to be returned int[] answer = new int[length]; // answer[i] contains the product of all the elements to the left // Note: for the element at index '0', there are no elements to the left, // so the answer[0] would be 1 answer[0] = 1; for (int i = 1; i < length; i++) { // answer[i - 1] already contains the product of elements to the left of 'i - 1' // Simply multiplying it with nums[i - 1] would give the product of all // elements to the left of index 'i' answer[i] = nums[i - 1] * answer[i - 1]; } // R contains the product of all the elements to the right // Note: for the element at index 'length - 1', there are no elements to the right, // so the R would be 1 int R = 1; for (int i = length - 1; i >= 0; i--) { // For the index 'i', R would contain the // product of all elements to the right. We update R accordingly answer[i] = answer[i] * R; R *= nums[i]; } return answer; }}/<code>複雜度分析
時間複雜度：O(N)，其中 N 指的是輸入數組的大小。
空間複雜度：O(1)，問題的描述中說明了輸出數組不算空間複雜度。
分享到:
閱讀更多 力扣LeetCode 的文章
