如何计算列表中除当前索引元素外其余所有元素的乘积

问题需求 #

现有列表 input_list = [1, 2, 3, 4, 5]，需要生成一个新列表，新列表每个位置的元素为原列表除当前索引对应元素外，其余所有元素的乘积。

示例 #

输入：

input_list1 = [1, 2, 3, 4, 5]

输出逻辑说明：第一个位置的结果是原列表除第一个元素外所有元素的乘积 2*3*4*5 = 120，其余位置计算规则一致，最终预期输出为：

prod = [120, 60, 40, 30, 24]

实现方案 #

方案1：暴力遍历法（时间复杂度O(n²)，适合短列表场景） #

对每个索引直接遍历全列表，跳过当前元素计算乘积：

def product_except_self(nums):
    n = len(nums)
    res = []
    for i in range(n):
        product = 1
        for j in range(n):
            if i != j:
                product *= nums[j]
        res.append(product)
    return res

# 调用测试
input_list = [1,2,3,4,5]
print(product_except_self(input_list))
# 输出：[120, 60, 40, 30, 24]

方案2：左右乘积数组法（时间复杂度O(n)，效率更高） #

分别计算每个位置左侧所有元素的乘积、右侧所有元素的乘积，最后对应位置左右乘积相乘得到结果：

def product_except_self(nums):
    n = len(nums)
    left_prod = [1]*n
    right_prod = [1]*n
    res = [1]*n
    
    # 计算每个位置左侧所有元素的乘积
    for i in range(1, n):
        left_prod[i] = left_prod[i-1] * nums[i-1]
    # 计算每个位置右侧所有元素的乘积
    for i in range(n-2, -1, -1):
        right_prod[i] = right_prod[i+1] * nums[i+1]
    # 左右乘积相乘得到最终结果
    for i in range(n):
        res[i] = left_prod[i] * right_prod[i]
    return res

# 调用测试
input_list = [1,2,3,4,5]
print(product_except_self(input_list))
# 输出：[120, 60, 40, 30, 24]

方案3：空间优化版（空间复杂度O(1)，输出数组不计入额外空间） #

不需要单独存储左右乘积数组，直接在结果数组上先存储左侧乘积，再动态计算右侧乘积合并结果：

def product_except_self(nums):
    n = len(nums)
    res = [1]*n
    # 先存储左侧乘积
    for i in range(1, n):
        res[i] = res[i-1] * nums[i-1]
    # 动态计算右侧乘积并合并到结果
    right = 1
    for i in range(n-1, -1, -1):
        res[i] *= right
        right *= nums[i]
    return res

# 调用测试
input_list = [1,2,3,4,5]
print(product_except_self(input_list))
# 输出：[120, 60, 40, 30, 24]

内容的提问来源于stack exchange，提问作者Hamza