0%

构建乘积数组

发表于 更新于

给定一个数组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]。不能使用除法。

先算A[0]*A[1]*...*A[i-1]，再乘A[i+1]*...*A[n-1]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    vector<int> multiply(const vector<int>& A) {
        const int size = A.size();
        if (size < 1)
        {
            return {};
        }
        else
        {
            vector<int> B(size);
            int t = 1;
            B[0] = 1;
            for (int i = 1; i < size; i++)
            {
                B[i] = B[i - 1] * A[i - 1];
            }
            for (int i = size - 2; i >= 0; i--)
            {
                t *= A[i + 1];
                B[i] *= t;
            }
            return B;
        }
    }
};