构建乘积数组

题目描述

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

解法

如果可以用除法，直接求出Ａ的总乘积，然后再除以某个Ａ［ｉ］就好了；

这里可以先从头到尾将Ａ［０］～Ａ［ｉ－１］依次乘起来，先放到Ｂ中；然后再从尾到头乘上去，依次和Ｂ中的值乘并存入Ｂ中；

代码

   vector<int> multiply(const vector<int>& A) {
        vector<int> B(A.size());
        int length = A.size();
        if(length<=1) return B;
        B[0] = 1;
        for(int i = 1;i<length;i++){
            B[i] = B[i-1] * A[i-1];
        }
        
        int temp = 1;
        for(int i = length-2;i>=0;--i){
            temp*=A[i+1];
            B[i]*=temp;
        }
        return B;
    }