51 构建乘积数组

题目描述

给定一个数组A[0,1,...,n-1]，请构建一个数组B[0,1,...,n-1]，其中B中的元素B[i]=A[0]A[1]...A[i-1]A[i+1]...A[n-1]。不能使用除法。

解题思路

核心思想：分别计算左乘积和右乘积。

关键步骤：

1. B[i] = A[0]A[1]...A[i-1] × A[i+1]...A[n-1]
2. 左乘积：从左到右累积
3. 右乘积：从右到左累积

时间复杂度：O(n) 空间复杂度：O(n)

Python 实现

def multiply(A):
    """
    构建乘积数组

    Args:
        A: 输入数组

    Returns:
        list: 乘积数组B
    """
    if not A:
        return []

    n = len(A)
    B = [1] * n

    # 计算左乘积
    left = 1
    for i in range(n):
        B[i] = left
        left *= A[i]

    # 计算右乘积并乘到B上
    right = 1
    for i in range(n - 1, -1, -1):
        B[i] *= right
        right *= A[i]

    return B


# 测试代码
if __name__ == "__main__":
    test_cases = [
        [1, 2, 3, 4, 5],
        [2, 3, 4],
        [1, 1, 1],
    ]

    for A in test_cases:
        B = multiply(A)
        print(f"A: {A}")
        print(f"B: {B}")
        print()

# 输出:
# A: [1, 2, 3, 4, 5]
# B: [120, 60, 40, 30, 24]
#
# A: [2, 3, 4]
# B: [12, 8, 6]
#
# A: [1, 1, 1]
# B: [1, 1, 1]

图解

示例: A = [1, 2, 3, 4, 5]

B[i] = A[0]A[1]...A[i-1] × A[i+1]...A[n-1]

步骤1: 计算左乘积
B[0] = 1 (左边没有元素)
B[1] = 1 (A[0])
B[2] = 2 (A[0]A[1])
B[3] = 6 (A[0]A[1]A[2])
B[4] = 24 (A[0]A[1]A[2]A[3])
B = [1, 1, 2, 6, 24]

步骤2: 计算右乘积
i=4: B[4] *= 1 = 24, right = 5
i=3: B[3] *= 5 = 30, right = 20
i=2: B[2] *= 20 = 40, right = 60
i=1: B[1] *= 60 = 60, right = 120
i=0: B[0] *= 120 = 120

最终B: [120, 60, 40, 30, 24]