【剑指 offer】构建乘积数组。

1、题目描述

给定一个数组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]

思考题：

• 能不能只使用常数空间？（除了输出的数组之外）

2、问题描述：

3、问题关键：

4、C++代码：

class Solution {
public:
    vector<int> multiply(const vector<int>& A) {
        //正着走一趟，反着走一趟
        //  1, A[0], A[0]*A[1], A[0]*A[1]*A[2],...A[0]*A[1] *...A[n - 1];
        // B[n - 1] * 1, B[n - 2] * A[n - 1] * A[n-2],...,B[1] * A[n - 1]*...A[2];
        if(A.empty()) return vector<int> ();
        int n = A.size();
        vector<int> B(n);
        for (int i = 0, tmp = 1; i < n; i ++) {
            B[i] = tmp;
            tmp = tmp * A[i];
        }
        for (int i = n - 1, tmp = 1; i >=0; i --) {
            B[i] *= tmp;
            tmp = tmp * A[i];
        }
        return B;
    }
};