构建乘积数组

题目描述

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

代码

class Solution {
public:
    vector<int> multiply(const vector<int>& A) {
    	vector<int> m(A.size(), 0);//记录A[0, i]的乘积
        if (A.size() > 0) {
            m[0] = A[0];
            for (int i = 1; i < A.size(); ++i) {
                m[i] = m[i - 1] * A[i];
            }
            
            int t = 1;
            for (int i = A.size() - 1; i > 0; --i) {
                m[i] = m[i - 1] * t;
                t *= A[i];
            }
            m[0] = t;
        }
        return m;
    }
};