题解 | #除自身以外数组的乘积#

题目分析

1. 题目给出了我们一个列表
2. 我们要返回一个列表，其中列表的每一项代表列表该数字左边的所有数字和右边的所有数字的乘积（不含本身），不使用除法操作

方法一：维护两个乘积列表

• 实现思路
  • 我们通过一次遍历，维护一个left和一个right列表
  • 对于每一个i位置的数字，left[i]表示数字nums[i]左边所有的数字之积，right[i]表示数字nums[i]右边所有的数字之积。
  • 在计算返回数组时，根据位置将left[i]和right[i]乘在一起即可

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param nums int整型一维数组 
# @return int整型一维数组
#
class Solution:
    def timesExceptSelf(self , nums: List[int]) -> List[int]:
        # write code here
        left = [1] * len(nums)
        right = [1] * len(nums)
        for i in range(1, len(nums)):
            left[i] = nums[i-1] * left[i-1]            # 表示i左边的乘积之和
            right[len(nums)-i-1] = nums[len(nums)-i] * right[len(nums)-i]  #表示i右边的乘积之和
        return [left[i] * right[i] for i in range(len(nums))]

复杂度分析

• 时间复杂度：$O(n)O(n)$，一趟遍历的空间开销
• 空间复杂度：$O(n)O(n)$，维护两个列表的常量空间开销

方法二：空间优化

• 实现思路

  • 我们将返回的res数组当作方法一中的left

  • 我们将题目的nums数组当作方法一中的right

  • 但是在处理右侧数字乘积的时候会有一个覆盖的问题，所以要在本轮存下当前数字，在下一轮时候用

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param nums int整型一维数组 
# @return int整型一维数组
#
class Solution:
    def timesExceptSelf(self , nums: List[int]) -> List[int]:
        # write code here
        res = [1] * len(nums)
        tmp1 = nums[len(nums)-1]                     # 保存最末尾nums数字
        for i in range(1, len(nums)):
            res[i] = res[i-1] * nums[i-1]            # res起到方法一中left的作用
        nums[len(nums)-1] = 1                        # nums起到方法一中right的作用
        for i in range(len(nums)-2, -1, -1):
            tmp2 = nums[i]
            nums[i] = tmp1 * nums[i+1]               # 由于这里会覆盖nums[i]，所以才有tmp1和tmp2实时保存一些值避免被覆盖
            tmp1 = tmp2
        for i in range(len(nums)):
            res[i] *= nums[i]
        return res

复杂度分析

• 时间复杂度：$O(n)O(n)$，常数趟遍历的时间开销
• 空间复杂度：$O(1)O(1)$，未引入额外的空间开销