Python programming question 42 -- product of elements other than itself

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 number Second number Third number Fourth number
All elements of a given list 1 2 3 4
The product of the left part of the current element 1 1 1 * 2 1 * 2 * 3
The product of the right part of the current element 2 * 3 * 4 3 * 4 4 1
Left product * right product 1 * 2 * 3 * 4 1 * 3 * 4 1 * 2 * 4 1 * 2 * 3 * 1
Calculate the final result 24 12 8 6
• 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 = , 
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 =  * 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, resMultiply left accumulation, resMultiply right accumulation;
i=1, resMultiply left accumulation, resMultiply right accumulation;
i=2, resMultiply left accumulation, resMultiply right accumulation;
i=3, resMultiply left accumulation, resMultiply right accumulation
"""
res =  * 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...)

Added by Weiry on Sun, 09 Jan 2022 10:13:31 +0200