剑指Offer-51.构建乘积数组(C++/Java)

题目：

给定一个数组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[0]*A[1]*......*A[n-1]/A[i]，由于题目要求不能使用除法，所以我们不能使用这种方法求B。

考虑将A[0]*A[1]*...*A[i-1]*A[i+1]*...*A[n-1]分成两部分求解，其中C[i] = A[0]*A[1]*...*A[i-1]，D[i] = A[i+1]*...*A[n-1]，那么B[i] = C[i] * D[i]。

实际上C[i] = C[i-1] * A[i-1]而D[i] = D[i+1] * A[i+1]。

我们可以先遍历一遍A，求的D，然后再利用B[i] = C[i] * D[i]，求出B[i]，而C[i] = C[i-1] * A[i-1]，不再需要循环求解，每次乘上A[i-1]即可。

程序：

C++

class Solution {

public:

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

        int length = A.size();

        vector<int> res(A.size(), );

        //D[i] = D[i+1]*A[i+1]

        for(int i = length-; i >= ; i--){

            res[i] = res[i+]*A[i+];

        }

        int temp = ;

        for(int i = ; i < length; ++i){

            //B[i] = C[i] * D[i]

            res[i] = temp * res[i];

            //C[i] = C[i-1]*A[i-1]

            temp *= A[i];

        }

        return res;

    }

};

Java

import java.util.ArrayList;

public class Solution {

    public int[] multiply(int[] A) {

        int[] res = new int[A.length];

        res[res.length-1] = 1;

        for(int i = res.length-2; i >= 0; --i){

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

        }

        int temp = 1;

        for(int i = 0; i < A.length; ++i){

            res[i] = temp * res[i];

            temp *= A[i];

        }

        return res;

    }

}

巴特西

剑指Offer-51.构建乘积数组(C++/Java)

题目：

分析：

程序：

最新文章

热门文章