题解 | #构建乘积数组#

构建乘积数组：最直观的想法是，将数组a中的所有元素进行相乘得到multiply，然后数组b中的每一个元素则等于multiply除以对应下标的a元素。但是存在一个问题，即数组元素可能为0，可能一个0也可能多个0，所以在计算乘积时需要进行单独计算，在处理元素时也需要进行单独处理。

    vector<int> multiply(const vector<int>& A) {
        // multiply_nozero表示A数组所有非零元素的乘积
        long long int multiply_nozero=1;
        // zero_num表示0元素的个数 避免求B[i]时有多个0
        int zero_num=0;
        // n表示A数组长度 由于常用故设置一个变量保存
        int n=A.size();
        // 求乘积
        for(int i=0;i<n;i++)
        {
            if(A[i]!=0)
                multiply_nozero*=A[i];
            else
                zero_num++;
        }
        // 构建B数组
        vector<int> B(n);
        // 设置B数组各元素
        for(int i=0;i<n;i++)
            if(A[i]==0&&zero_num==1)
                B[i]=multiply_nozero;
            else if(zero_num==0)
                B[i]=multiply_nozero/A[i];
            else
                B[i]=0;
        return B;
    }

idea：但是题目中明确要求不能使用除法，那么应该怎么办呢？我们不妨找找规律。假设以B[i]表示横坐标，以A[i]表示纵坐标，构成一个大小为A数组长度的二维数组，其中以对角线作为划分，每一行都分为左半部分left和右半部分right，B[i]即等于其左半部分与右半部分相乘的结果，其中，左半部分left构成下三角，其从上到下依次计算，右半部分right构成上三角，其从下到上依次计算。具体实现方法如下：首先将B数组每一个元素均初始化为1，然后从左向右遍历A数组，先使用左半部分计算B[i]，其等于B的上一个元素B[i-1]乘以A的上一个元素A[i-1]，然后使用temp表示右半部分乘积结果，其被初始化为1，从右向左遍历A数组，其先使用右半部分temp乘以原先已经被左半部分计算得到的B[i]，然后再使用A[i]元素更新temp，以供下次使用，一定注意错位关系。(手动模拟)

vector<int> multiply(const vector<int>& A) 
{
     // n表示A数组长度 由于常用故设置一个变量保存
     int n=A.size();
     // 构建B数组 初始均为1
     vector<int> B(n,1);
     // 先从左向右遍历A
     for(int i=1;i<n;i++)
        // B数组各个元素的左边部分 其为B数组前一个元素乘以A数组前一个元素
        B[i]=B[i-1]*A[i-1];
     // temp表示B数组右半部分乘积结果
     int temp=1;
     for(int i=n-1;i>=0;i--)
     {
         // B[i]原先已经计算完左半部分 现在乘以右半部分
         B[i]*=temp;
         // temp更新 注意错位
         temp*=A[i];
     }
     return B;
}