Java不使用嵌套循环实现List除自身外元素乘积功能

核心逻辑 #

输出数组第i位的值等于输入数组中除第i位外所有元素的乘积，示例如下：

输入示例：inputList = [1, 2, 3, 4]
预期输出：outputList = [24, 12, 8, 6]

实现思路 #

通过两次单向遍历分别计算每个位置的左侧乘积和右侧乘积，对应位置相乘即可得到结果，全程仅使用独立单层循环，无嵌套结构：

• 第一次从左到右遍历，计算每个位置左侧所有元素的乘积，存入结果数组对应位置
• 第二次从右到左遍历，计算每个位置右侧所有元素的乘积，和结果数组中已存储的左侧乘积相乘，直接得到最终结果
• 不需要额外存储左右乘积数组，直接在结果数组上迭代计算即可，额外空间开销为常数级

代码实现（Python） #

def product_except_self(nums):
    length = len(nums)
    result = [1] * length
    # 计算左侧乘积
    left_temp = 1
    for i in range(length):
        result[i] = left_temp
        left_temp *= nums[i]
    # 计算右侧乘积并合并得到最终结果
    right_temp = 1
    for i in range(length - 1, -1, -1):
        result[i] *= right_temp
        right_temp *= nums[i]
    return result

# 测试示例
input_list = [1, 2, 3, 4]
print(product_except_self(input_list)) # 输出 [24, 12, 8, 6]

方案优势 #

• 时间复杂度为O(n)，仅需两次遍历数组，性能远高于嵌套循环的O(n²)实现
• 未使用除法运算，即使输入数组存在0元素也可以正确计算，不会触发除零异常
• 空间开销低，仅需两个临时变量存储乘积值

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