subject

Given a list of integers with a length of ＾ n ＾ nums, where ＾ n > 1, the output list ＾ res is returned, where res[i] is equal to the product of other elements in ＾ nums ＾ except ＾ nums[i].

For example:

Given a list: [1, 2, 3, 4], return result: [24, 12, 8, 6]

Note: Division is not allowed in the implementation process, and the time complexity is required to be O(n)

Realization idea

• Traverse the list. For the current element traversed, if we want to calculate the product of integers other than itself, we only need to find the product of all elements on the left and the product of all elements on the right. Assuming that the given list is: [1, 2, 3, 4], the specific calculation process is as follows:

• First, the positive order traversal is used to find the product of all elements on the left side of each element, and the results are saved to left_product_list
• Then, traverse in reverse order, find the product of all elements on the right side of each element, and save the result to right_product_list
• Finally, for each element traversed, the final product result = left product * right product, save the result to a list, and finally return

code implementation

def productExceptSelf(nums):
    res = []
    left_product_list, right_product_list = [1], [1]
    left_product, right_product = 1, 1
    for i in range(1, len(nums)):  # Starting with the first element, the product of all elements to the left of each element is calculated
        left_product *= nums[i - 1]
        left_product_list.append(left_product)
    for i in range(len(nums) - 2, -1, -1):  # Starting from the penultimate element, calculate the product of all elements to the right of each element
        right_product *= nums[i + 1]
        right_product_list.append(right_product)
    for i in range(len(nums)):  # Attention left_product_list is a positive order calculation, right_product_list is calculated in reverse order
        left, right = left_product_list[i], right_product_list[len(nums) - 1 - i]
        res.append(left * right)
    return res

In the above implementation, we have specifically defined two lists: left_product_list,right_product_list, which records the left element product and the right element product respectively. The space complexity here is O(n). If we do not consider returning the list space, we can actually optimize the above code to reduce its space complexity to constant level O(1):

def productExceptSelf(nums):
    res = [1] * len(nums)
    left_product, right_product = 1, 1
    for i in range(1, len(nums)):  # Starting with the first element, the product of all elements to the left of each element is calculated
        left_product *= nums[i - 1]
        res[i] *= left_product
    for i in range(len(nums) - 2, -1, -1):  # Starting from the penultimate element, calculate the product of all elements to the right of each element
        right_product *= nums[i + 1]
        res[i] *= right_product
    return res

In the above implementation, we no longer use additional lists to save the product of left and right elements, but set the final return list as a fixed length list, and then directly modify the element values in the list. In this way, the space complexity will be reduced to O(1) without considering the return list space.

From the above code, we can find that we have traversed the list twice. The first positive order traversal is to calculate the left product, and the second reverse order traversal is to calculate the right product. In fact, we can continue to optimize here, only through one traversal. The final optimized code is as follows:

def productExceptSelf(nums):
    """
    in the light of [1, 2, 3, 4] ，During traversal, the left and right cumulants of each element are multiplied
    i=0, res[0]Multiply left accumulation, res[3]Multiply right accumulation;
    i=1, res[1]Multiply left accumulation, res[2]Multiply right accumulation;
    i=2, res[2]Multiply left accumulation, res[1]Multiply right accumulation;
    i=3, res[3]Multiply left accumulation, res[0]Multiply right accumulation
    """
    res = [1] * len(nums)
    left_product, right_product = 1, 1
    for i in range(len(nums)):
        res[i] *= left_product
        left_product *= nums[i]  # The accumulation of all elements to the left of the subscript i position element
        res[len(nums) - 1 - i] *= right_product
        right_product *= nums[len(nums) - 1 - i]  # The subscript len - 1 - i is the accumulation of all elements to the right of the position element
    return res

More Python programming questions are waiting for you to challenge: Python programming problem summary (continuously updated...)