【剑指Offer】面试题52：构建乘积数组

一：题目描述

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

二：解题分析

我的碎碎念....

//B[i]=A中所有数相乘，那么，B中所有元素不就是一样的么？
//和除法又有什么关系？
//感觉自己没有读懂题
//傻了吧，不认真读题，明明B[i]=A中除了i以外的所有元素相乘
//如果可以使用除法先计算A中所有元素的结果S，B[i]=S/A[i] ,但要注意A[i]为0的情况

//不用除法，可以使用双层for循环，计算B[i]的值，时间复杂度O（n2）,不建议
//其实对于B的求解，相当于用A构造一个n*n的矩阵，每一行代表向量A，重点在于对角线为1，代表A[i]不参与第i行的运算
//1 A[1] A[2] A[3]... A[N-2] A[N-1]
//A[0] 1 A[2] A[3] A[N-2] A[N-1]
//A[0] A[1] 1 A[4] A[N-2] A[N-1]
//...
//A[0] A[1] A[2]................A[N-1]
//A[0] A[1] A[2]................ 1
//一种巧妙地方法就是利用两个数组，分别保存A中0--i-1相乘的结果， i+1---n-1相称的结果
//A中0--i-1
//1
//A[0]
//A[0] A[1]
//A[0] A[1] A[2]
//...
//A[0] A[1] A[2] .... A[n-1]
//可以利用自上而下的解法推导出C[0]=1 C[i]=C[i-1]*A[i-1]
//A中i+1 --- n-1
//A[1] A[2] ... A[n-1]
// A[2] ...A[n-1]
//...
// A[n-1]
// 1
//可以利用自下而上的方法推导出D[n-1]=1, D[i]=D[i+1]*A[i+1]

三：代码实现

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