给定一个数组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[0]~A[i - 1] 的乘积 和 A[i + 1]~A[n - 1]的乘积。
可以用两个for循环，一次计算0~i-1的乘积，一次计算i+1~n-1的乘积。
注意：A[0]*A[0-1] 按 1算 A[n - 1 + 1]*A[n - 1]也按 1 算。
精简的代码：
vector<int> multiply2(const vector<int>& A)
{
if(A.size() < )
return vector<int>(); vector<int> B;
int value = ;
B.push_back(value);
for(int i = ; i < A.size(); i++)
{
value *= A[i - ];
B.push_back(value);
}
value = ;
for(int i = A.size() - ; i >= ; i--)
{
value *= A[i + ];
B[i] *= value;
}
return B;
}
我自己写的，用了过多的冗余空间。
vector<int> multiply(const vector<int>& A) {
if(A.size() < )
return vector<int>();
vector<int> B;
vector<int> M0(A.size(), ), Mn(A.size(), );
M0[] = A[];
Mn.back() = A.back();
for(int i = ; i < A.size() - ; i++)
M0[i] = M0[i - ] * A[i];
for(int i = A.size() - ; i >= ; i--)
Mn[i] = Mn[i + ] * A[i];
for(int i = ; i < A.size(); i++)
{
int b = ((i - < ) ? : M0[i - ]) * ((i + >= A.size()) ? : Mn[i + ]);
B.push_back(b);
}
return B;
}