## 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 = [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...)