Алгоритмический вопрос дня — leetcode 238 — произведение массивов, отличных от самих себя — python

【Название Описание】

【Идея кода】

Этот вопрос в основном потому, что в основе вопроса есть требования.Во-первых, деление не допускается, что развеивает мою идею сначала найти произведение кумулятивного умножения массива, а затем делить на каждое nums[i]. Во-вторых, требуется, чтобы временная сложность была линейной, поэтому двухуровневая вложенность циклов невозможна.

Поэтому, учитывая левый и правый массивы, левый массив хранит произведение всех элементов до nums[i], а правый массив хранит произведение всех элементов после nums[i]. Таким образом, чтобы найти output[ i] is Вы можете напрямую умножать левый и правый массивы на соответствующие позиции. Временная сложность этого метода линейна, пространственная сложность — O(1), и требуется только одно место для хранения переменных num.

Позвольте мне рассказать об этом здесь Способ умножения левого и правого массивов в соответствующей позиции использует функцию карты и функцию zip в python.

left=[1,2]
right=[3,4]
output=list(map(lambda x:x[0]*x[1],list(zip(left,right ))))

【Исходный код】

class Solution(object):
    def productExceptSelf(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        left=[]
        right=[]
        num=1
        for i in range(len(nums)):
            left.append(num)
            num*=nums[i]
        num=1
        for i in reversed(range(len(nums))):
            right.append(num)
            num*=nums[i] 
        return map(lambda (x,y):x*y,zip(left,reversed(right) ))