【Leetcode 筆記】 238. Product of Array Except Self

題目解釋

給定一個整數陣列 nums，傳回一組 answer 的 array，使得 answer[i] 等於 nums 中除 nums[i] 之外的所有元素的乘積。

演算法的 time complexity 必須是 O(n) 且 不使用除法運算。

範例

• 輸入: nums = [1, 2, 3, 4]
• 輸出: [24, 12, 8, 6]

輸出中的第一個元素 24 是因為他捨去了 1 (nums[0])，只留 2 * 3 * 4 = 24，
輸出中的第二個元素 12 是因為他捨去了 2 (nums[1])，只留 1 3 4 = 12，
其他以此類推…。

最佳解法

令兩條長度與 nums 相同的全 1 array：

• from_left： 從左邊開始走
• from_right：從右邊開始走

注意

from_left 不是 [1, 2, 6, 24]！
from_right 也不是 [24, 24, 12, 4]！

他實際上是先 assign from_left 跟 from_right 的值才乘上 nums[i] 的值，可以把它想成他從起點開始時總會慢一拍，且起點的數值都是 "1"。

所以最後兩條 array 的值是

• from_left = [1, 1, 2, 6]
• from_right = [24, 12, 4, 1]

code 如下。

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        length = len(nums)
        from_left, from_right = [1] * length, [1] * length

        left_product = 1
        for i in range(length):
            from_left[i] = left_product
            left_product *= nums[i]

        right_product = 1
        for i in range(length - 1, -1, -1):
            from_right[i] = right_product
            right_product *= nums[i]

        res = [i * j for i, j in zip(from_left, from_right)]
        return res

時間複雜度

O(n)，n 是 nums 的元素個數，不過我們總共走了三次。

空間複雜度

O(n)，不過我們總共存了三次。

結語

一時寫一時忘，一直寫一直忘…

• About
• Latest Posts

數據女巫 𝔻.𝕡𝕪𝕤

𝐀𝐈 𝐀𝐫𝐭𝐢𝐬𝐭 • 𝐒𝐨𝐟𝐭𝐰𝐚𝐫𝐞 𝐄𝐧𝐠𝐢𝐧𝐞𝐞𝐫
﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊
致力於打破現有框架的 AI 藝術創作者，曾接受藝文雜誌的個人專訪，作品於香港實體展出。有擔任大學講座講師與 Stable Diffusion AI 年會講者的經驗。擅長 Live Prompting，曾獲 GIGABYTE VS AI 街頭對戰冠軍、ASUS 校園 AI 繪圖競賽亞軍等殊榮。
---
歡迎合作邀約 / 委託 / 各式交流
ᴇᴍᴀɪʟ：dpys@techmagichouse.art

Latest posts by 數據女巫 𝔻.𝕡𝕪𝕤 (see all)

• [推薦工具] 讓程式碼截圖變的美美的吧！VScode CodeSnap 與 3 種同功能線上工具介紹 - 2025-01-05
• [AI 繪圖初級教學] 用 X/Y/Z Plot 比較 Stable Diffusion 的 prompt 與 LoRA 效果 - 2024-12-27
• [AI 繪圖中級篇教學] Stable Diffusion WebUI WD14 Tagger 介紹 - 2024-12-26