https://leetcode.com/problems/product-of-array-except-self/#/description

image.png

分析

• 將某個元素 左邊所有元素相乘 * 右邊所有元素相乘 返回即可

Python 超時版

• 16/17 有個超長的列表又尼瑪超時了。。。
• Time O(n^2)
• Space O(n)

class Solution(object):
    def productExceptSelf(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        nn = []
        for i in range(len(nums)):
            nn.append(self.pro(nums, 0, i) * self.pro(nums, i+1, len(nums)))
        return nn
    
    def pro(self, nums, start, end):
        s = 1
        for i in range(start, end):
            s *= nums[i]
        return s

繼續(xù)分析

• 假設(shè)有一個列表pro_before = [..pro(nums, 0, i)..]
• 有個列表pro_after = [...pro(nums, i, len(nums)..]
• 那么本題的解為pro_before[i] * pro_after[i]
• 而上述兩個列表只需要正向 反向掃描nums即可
• 這樣只有線性掃描 Time O(n)
• 注意這里pro_before * pro_after 所以實際上都是連乘在里面所以不需要開兩個數(shù)組
• 只需要初始化res為全1的數(shù)組即可
• Space O(n)

image.png

Python

class Solution(object):
    def productExceptSelf(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        res = [1] * len(nums)
        t = 1
        for i in range(len(nums)):
            res[i] *= t
            t *= nums[i]
        t = 1
        for i in range(len(nums) - 1, -1, -1):
            res[i] *= t
            t *= nums[i]
        return res