题目描述

给定一个数组$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, 2, 3, 4, 5]

输出：[120, 60, 40, 30, 24]

算法

(模拟) $O(n)$

$B[i]=A[0]×A[1]×… ×A[i-1]×A[i+1]×…×A[n-1]$，将其拆成两部分进行计算

1. 先计算 $A[i]$ 左边，$A[0]×A[1]×… ×A[i-1]$ 的结果
2. 再计算 $A[i]$ 右边，$A[i+1]×…×A[n-1]$ 的结果

时间复杂度

需要遍历两次数组，时间复杂度为 $O(n)$

C++ 代码

class Solution {
public:
    vector<int> multiply(const vector<int>& A) {
        int n = A.size();
        vector<int> B(n);

        for (int i = 0, p = 1; i < n; i ++ )
        {
            B[i] = p;
            p *= A[i];
        }

        for (int i = n - 1, p = 1; i >= 0; i -- )
        {
            B[i] *= p;
            p *= A[i];
        }

        return B;
    }
};