题目简述

            构建B数组，使得 B[i] 的值等于 A数组中除了A[i]以外所有元素的乘积（不能使用除法）。

算法一:

        时间复杂度：O(N2)

        思路：

            将B数组初始化为1，对于每个 B[i] ,都遍历一遍A数组，让 B[i] 乘上除了 A[i] 以外所有元素的值 。

        代码: 

class Solution {
public:
    vector<int> multiply(const vector<int>& A) {
        vector<int> B(A.size(),1);//将B数组初始化为1
        for(int i=0;i<A.size();i++){
            for(int j=0;j<A.size();j++){
                if(j!=i)//若不是A[i],则B[i]乘上A[j]
                    B[i]*=A[j];
            }
        }
        return B;
    }
};

        算法二:

        时间复杂度：O(N)

        思路:

                分两次操作
                        第一步：  使 B[i] = A[0] * A[1] * ... * A[i-1] 。
                                        这一步我们直接利用递推 B[i] = B[i-1] * A[i-1] ，便能线性完成。
                        第二步：  让 B[i] 乘上 A[i+1] ~ A[n-1] 的值即可
                                        具体操作：我们可以从后往前遍历，用right表示第i个元素右边所有元素的乘积。
                                                          即 rigth = A[i+1] * A[i+2] * ... * A[n-1]，由于从后往前遍历，第i个位置时，right每次都乘上 A[i+1]，便能线性处理。
                                                          后让B[i]乘上right便能使 B[i] 满足题目的构建。

图解：

代码: 

class Solution {
public:
    vector<int> multiply(const vector<int>& A) {
        vector<int> B(A.size(),1);
        for(int i=1;i<A.size();i++){
            B[i]=B[i-1]*A[i-1];
        }
        int right=1;
        for(int i=A.size()-2;i>=0;i--){
            right*=A[i+1];
            B[i]*=right;
        }
        return B;
    }
};