LeetCode如何構(gòu)建乘積數(shù)組

題目描述

給定一個數(shù)組 A[0,1,…,n-1]，請構(gòu)建一個數(shù)組 B[0,1,…,n-1]，其中 B 中的元素 B[i]=A[0]×A[1]×…×A[i-1]×A[i+1]×…×A[n-1]。不能使用除法。

• 所有元素乘積之和不會溢出 32 位整數(shù)
• a.length <= 100000

題目樣例

示例

• 輸入: [1,2,3,4,5]
• 輸出: [120,60,40,30,24]

題目思考

1. 如何做到 O(N)時間復(fù)雜度?

解決方案

思路

• 一個比較容易想到的思路是暴力法, 對每個元素都計算其左右乘積, 這樣時間復(fù)雜度達(dá)到了 O(N^2), 按照題目數(shù)據(jù)規(guī)?？隙〞瑫r
• 還有種方法是求所有元素的總乘積, 然后對于每個元素分別除以自身 (注意對 0 的處理), 這樣雖然只用了 O(N)時間, 但不滿足題目要求
• 那如何做到 O(N)時間復(fù)雜度且不使用除法呢? 我們?nèi)绻軌蛟谟嬎隳硞€元素時利用到之前的計算結(jié)果, 那么就不需要重復(fù)計算當(dāng)前的左右所有乘積了
• 比較容易想到的思路就是類似前綴和的預(yù)處理方案, 只是這里改成了                           前綴積, 具體步驟如下:
1. 從左到右遍歷一遍數(shù)組, 記錄當(dāng)前前綴積并保存到數(shù)組中
2. 然后再從右向左遍歷, 記錄當(dāng)前后綴積, 然后與前一個前綴積相乘, 即為當(dāng)前元素的左右所有元素乘積了
• 下面的代碼對必要步驟有詳細(xì)的解釋, 方便大家理解

復(fù)雜度

• 時間復(fù)雜度 O(N): 只需要遍歷數(shù)組兩次
• 空間復(fù)雜度 O(N): 需要維護(hù)一個前綴積數(shù)組

代碼

class Solution:
    def constructArr(self, a: List[int]) -> List[int]:
        # 從左到右, 再從右向左遍歷
        # 維護(hù)前綴積數(shù)組, 從右向左遍歷時只需要維護(hù)后綴積即可, 然后乘以前一個前綴積, 其結(jié)果即為當(dāng)前元素的左右元素乘積
        lefts = []
        left = 1
        for x in a:
            left *= x
            lefts.append(left)
        # 這里只需要維護(hù)后綴積, 沒必要再建立一個后綴積數(shù)組
        right = 1
        res = [0] * len(a)
        for i in range(len(a))[::-1]:
            # 注意下標(biāo)為0時左側(cè)沒有元素, 此時左側(cè)部分乘積置為1
            left = lefts[i - 1] if i > 0 else 1
            res[i] = left * right
            # 注意當(dāng)前元素處理完之后再乘以它, 因為結(jié)果是不包含當(dāng)前元素自身的
            right *= a[i]
        return res