题目描述
描述：给定一个数组 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]（除 A[i] 以外的全部元素的的乘积）。程序中不能使用除法。（注意：规定 B[0] = A[1] * A[2] * … * A[n-1]，B[n-1] = A[0] * A[1] * … * A[n-2]）。
对于 A 长度为 1 的情况，B 无意义，故而无法构建，用例中不包括这种情况。
数据范围：1≤n≤10 ，数组中元素满足 ∣val∣≤10 。
输入：[1,2,3,4,5]
返回值：[120,60,40,30,24]
输入：[100,50]
返回值：[50,100]
解题思路
构建乘积数组：最直观的想法是，将数组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;
}