0238. Product of Array Except Self - chasel2361/leetcode GitHub Wiki

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]

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

這題要求算出 output[i] 相當於 nums[i] 以外所有值的積，不能使用乘法且時間複雜度必須為 O(N)

我一開始想不太出來要怎麼把時間複雜度降到 O(N)，只能用暴力解

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        sol = []
        for i in range(len(nums)):
            n = 1
            for num in nums[:i]+nums[i+1:]:
                n *= num
            sol.append(n)
        return sol

將除了 num[i] 以外的每個值都乘一遍，但這樣的時間複雜度是 O(N*(N-1)) = O(N**2)

仔細觀察後才發現，可以把解拆成 i 的左邊以及右邊兩組乘積，如果先把 sol 從左邊掃一遍，儲存左邊乘積，再利用一個暫存變數 tmp 儲存右邊乘積對 sol 相乘就可以達到原先的目的，將時間複雜度壓縮為 O(2N) = O(N)，且空間複雜度若不計輸出的 sol 為 O(1)。

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        """
        Example:
            nums    1        2        3        4
            res     2*3*4    1*3*4    1*2*4    1*2*3
            left             1        1*2      1*2*3
            right   2*3*4      3*4        4
        
        Args:
            n: number of nums
            sol: left
            tmp: right
        """        
        n = len(nums)
        sol = [1] * n
        for i in range(1, n):
            sol[i] = sol[i-1] * nums[i-1]
        tmp = 1
        for i in range(n-1, -1, -1):
            sol[i] *= tmp
            tmp *= nums[i]
        
        return sol