（剑指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]。不能使用除法。

思路：

方法1：

直接连乘n-1个数，得到B[i]；

时间复杂度：O(n^2)

方法2：

构建前向乘积数组C[i]=A[0]*A[1]*...*A[i-1]，即C[i]=C[i-1]*A[i-1]；

构建后向乘积数组D[i]=A[n-1]*A[n-2]*...A[n-i+1]，即D[i]=D[i+1]*A[i+1]；

通过C[i],D[i]来求B[i]：B[i]=C[i]*D[i]

时间复杂度：O(n)

代码：

void multiply(const vector<double>& array1,vector<double>& array2){

    int len1=array1.size();

    int len2=array2.size();

    if(len1==len2 && len2>1){

        array2[0]=1;

        for(int i=1;i<len1;i++){

            array2[i]=array2[i-1]*array1[i-1];

        }

        double tmp=1;

        for(int i=len1-2;i>=0;i--){

            tmp*=array1[i+1];

            array2[i]*=tmp;

        }

    }

}

在线测试OJ：

http://www.nowcoder.com/books/coding-interviews/94a4d381a68b47b7a8bed86f2975db46?rp=3

AC代码：

class Solution {

public:

    vector<int> multiply(const vector<int>& A) {

    	int len=A.size();

        if(len<1)

            return vector<int>();

        vector<int> B(len,1);

        for(int i=1;i<len;i++){

            B[i]*=B[i-1]*A[i-1];

        }

        int tmp=1;

        for(int i=len-2;i>=0;i--){

            tmp*=A[i+1];

            B[i]*=tmp;

        }

        return B;

    }

};

class Solution {

public:

    vector<int> multiply(const vector<int>& A) {

    	int len=A.size();

        if(len<1)

            return vector<int>();

        vector<int> B(len,1);

        vector<int> front(len,1);

        vector<int> back(len,1);

        for(int i=1;i<len;i++){

            front[i]=front[i-1]*A[i-1];

        }

        for(int i=len-2;i>=0;i--){

            back[i]=back[i+1]*A[i+1];

        }

        for(int i=0;i<len;i++)

            B[i]=front[i]*back[i];

        return B;

    }

};

巴特西

（剑指Offer）面试题52：构建乘积数组

题目：

思路：

代码：

在线测试OJ：

最新文章

热门文章