《剑指offer》-数组乘积，不使用除法

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

这题不准用除法，那么就转化。首先想到的是用“先取log再e回去”的做法，但是因为坑比较多，比如A[i]等于0的情况，log处理0不好弄。

但是这种思路并非一无是处。当发现log 0做不下去，就容易想到直接元素A[i]左右两侧各个元素的乘积left和right，它俩的乘积left x right就是最终的结果啊。

那么结果数组的每个元素B[i]就分解成左右两部分的乘积。代码就是网上找到的通用版本那个了。复杂度O(n^2)

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

        vector<int> left(A.size());
        left[0] = 1;

        cout << "left:" << endl;
        for (int i = 1; i<A.size(); i++){
            left[i] = left[i - 1] * A[i-1];
        }
        for (int i = 0; i < A.size(); i++){
            cout << left[i] << " ";
        }
        cout << endl;

        cout << "right:" << endl;
        vector<int> right(A.size());
        right[A.size()-1] = 1;
        for (int i = A.size()-2; i>=0; i--){
            right[i] = right[i + 1] * A[i+1];
            //cout << right[i] << " ";
        }
        for (int i = 0; i < A.size(); i++){
            cout << right[i] << " ";
        }
        cout << endl;

        for (int i = 0; i<B.size(); i++){
            B[i] = left[i] * right[i];
        }
        return B;
    }
};