面试题66:构建乘积数组

题目

给定一个数组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[i-1] * A[i+1] * .....* A[n-1]看成A[0] * A[1] * ..... * A[i-1] 和 A[i+1] * .....* A[n-1]两部分的乘积。

代码

1. 第一个for循环计算A[0] * A[1] * ..... * A[i-1]
2. 第二个for循环计算A[i+1] * .....* A[n-1]

class Solution{
  public:
    vector<int> multiply(const vector<int> &array1)
    {
        int length = array1.size();
        vector<int> B(length,1);
        for(int i = 1;i<length;++i)
        {
            B[i] = B[i-1]*array1[i-1];
            //cout << "B[i] :" << B[i] << endl;
        }
        
        int temp = 1;
        for(int i = length-2;i>=0;--i)
        {
            temp *= array1[i+1];
            B[i] *= temp;
            cout << "B[i] :" << B[i] << endl;
        }
        return B;
    }
};

完整代码见Github