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存储结果。