LeetCode 刷題紀錄｜238. Product of Array Except Self (Medium)

Roy Wang

Published in

RoyWannago

6 min readNov 15, 2020

Product of Array Except Self

Question

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

Example:

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

Constraint: It’s guaranteed that the product of the elements of any prefix or suffix of the array (including the whole array) fits in a 32 bit integer.

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.)

這題要算除了自己以外的其他數乘積，且不能用除的作法

Solutions

Solution 1: 暴力解 (TLE)

Complexity:

Time: O(n²)
Space: O(1)

Solution 2: Left and Right Product Lists

第一種解法的思路是我們記得自己的左邊（除了自己以外）的乘積，跟自己右邊的成績，答案就會是自己的左邊鄰居們 * 右邊鄰居們 = 全部鄰居們

我們來試試看實作上會長怎樣：

先來看左邊鄰居乘積怎麼做：

第一個數 4 的左邊沒有東西，所以設為 1

第二個數 5 的左邊是 4，所以左邊鄰居們乘積為 4

第三個數 1 的左邊是 5，所以左邊鄰居們的乘積為 4 * 5 = 20

第四個數 8 的左邊是 1，所以左邊鄰居們的乘積為 20 * 1 = 20

第五個數 2 的左邊是 8，所以左邊鄰居們的乘積為 20 * 8 = 160

寫成程式碼的感覺長這樣：

再來看右邊鄰居乘積怎麼做：

nums = [4, 5, 1, 8, 2]

這次要從最右邊開始，最右邊的數初始為 1 ➡️ [0, 0, 0, 0, 1]

倒數第二個數8的右邊鄰居是2，1 * 2 = 2 ➡️ [0, 0, 0, 2, 1]

再來1的右邊鄰居們有8跟2，8 * 2 = 16 ➡️ [0, 0, 16, 2, 1]

5的右邊鄰居們有1, 8跟2，1 * 16 = 16 ➡️ [0, 16, 16, 2, 1]

最後，4的右邊鄰居們就要再乘上5，16 * 5 = 80 ➡️ [80, 16, 16, 2, 1]

寫成程式碼：

const rightProductSoFar = Array(len).fill(0) 
// nums.length - 1 是最後一個數
rightProductSoFar[nums.length - 1] = 1 // nums.length - 2 是倒數第二個數開始，一直更新到 i = 0，i 逐漸遞減
for (let i = nums.length - 2; i >= 0; i--) {                
    rightProductSoFar[i] = nums[i+1] * rightProductSoFar[i+1]     
}

有了除自己以外兩邊鄰居乘積的數列後，就可以來算最後的總鄰居和

output[i] = L[i] * R[i]

結合在一起，最後程式碼長這樣：

/**
 * @param {number[]} nums
 * @return {number[]}
 */var productExceptSelf = function(nums) {
    const len = nums.length;
    const L = Array(len).fill(0)
    const R = Array(len).fill(0)    
    const output = Array(len).fill(0)
    
    L[0] = 1
    for (let i = 1; i < len; i++) {
        L[i] = nums[i-1] * L[i-1]
    }
    
    R[len-1] = 1
    for (let i = len-2; i >= 0; i--) {
        R[i] = nums[i+1] * R[i+1]
    }
    
    for (let i = 0; i < len; i++) {
        output[i] = L[i] * R[i]
    }
    
    return output;
};

Python:

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 reversed(range(length - 1)):
            R[i] = nums[i + 1] * R[i + 1]
        
        for i in range(length):
            answer[i] = L[i] * R[i]
        
        return answer

Complexity:

Time: O(n)
Space complexity : O(N) used up by the two intermediate arrays that we constructed to keep track of product of elements to the left and right.

Solution 3: O(1) 優化空間複雜度

題目說 answer array 不會增加空間複雜度，所以優化的作法試試看只用 answer array來先存左邊鄰居乘積和，再存乘上右邊鄰居和，就可以省下兩個array，讓空間複雜度降低為O(1)

var productExceptSelf = function(nums) {
    const len = nums.length;
    const output = Array(len).fill(0)
    
    output[0] = 1
    for (let i = 1; i < len; i++) {
        output[i] = nums[i-1] * output[i-1]
    }
    
    let R = 1
    for (let i = len-1; i >= 0; i--) {
        output[i] = output[i] * R
        R *= nums[i]
    }
    
    return output;
};

Complexity analysis

Time complexity : O(N)
Space complexity : O(1)

其他可以參考的影片：

新手上路，如果有寫錯的地方歡迎大力糾正，歡迎留言討論或是到我的Socials找我~謝謝觀看！

About Roy

Social Media
Facebook — RoyWannago
Twitter — @roywannago
Instagram — @royflwdesign
Website — roywannago.com

LeetCode 刷題紀錄 ｜238. Product of Array Except Self (Medium)