LeetCode如何构建乘积数组

问题描述

给定一个长度为 n 的数组 numbers，求一个长度为 n 的数组 output，其中 output[i] 等于除了 numbers[i] 之外其他所有元素的乘积。

解决思路

我们可以先计算出数组 numbers 中所有元素的乘积，然后再依次计算 output 数组中的每个元素。对于 output[i]，可以将 numbers[i] 排除在外，只计算其他元素的乘积。根据乘法的性质，可以将这个乘积分为两部分：numbers[i] 之前的所有元素的乘积和 numbers[i] 之后的所有元素的乘积。我们可以先计算出 numbers[i] 之前所有元素的乘积，再计算出 numbers[i] 之后所有元素的乘积，最后将这两个乘积相乘即可得到 output[i]。

算法实现

1. 首先计算数组 numbers 中所有元素的乘积，记为 totalProduct。

2. 初始化一个长度为 n 的数组 output，所有元素初始值为 1。

3. 遍历数组 numbers，对于每个元素 numbers[i]，依次计算 numbers[i] 之前所有元素的乘积，记为 preProduct，和 numbers[i] 之后所有元素的乘积，记为 postProduct。将 preProduct 和 postProduct 相乘得到 output[i] 的值。

4. 返回数组 output。

def constructProductArray(numbers):
    n = len(numbers)
    totalProduct = 1
    output = [1] * n

    # 计算数组numbers中所有元素的乘积
    for i in range(n):
        totalProduct *= numbers[i]

    # 计算output数组中每个元素的值
    for i in range(n):
        # 计算numbers[i]之前所有元素的乘积
        preProduct = 1
        for j in range(i):
            preProduct *= numbers[j]

        # 计算numbers[i]之后所有元素的乘积
        postProduct = 1
        for j in range(i+1, n):
            postProduct *= numbers[j]

        # 将preProduct和postProduct相乘得到output[i]的值
        output[i] = preProduct * postProduct

    return output

复杂度分析

该算法的时间复杂度为 O(n^2)，其中 n 为数组 numbers 的长度。这是因为对于每个元素 numbers[i]，我们需要遍历其之前的所有元素和之后的所有元素。空间复杂度为 O(n)，需要额外的数组 output 存储结果。