题目描述
给定一个数组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中的每个元素要乘的元素写成矩阵，其中A[i]置1，那么就是一个上三角和一个下三角，类似于下图：
![]() ![]() ![]() 那么B[i]就可以表示成C[i]*D[i]，就可以解决了。
代码：
class Solution {
public:
vector<int> multiply(const vector<int>& A) {
vector<int> B,C,D;
int len = A.size();
int t1=1,t2=1;
if(len==0)
return B;
C.push_back(t1);
D.push_back(t2);
for(int i=0;i<len-1;i++){
t1*=A[i];
t2*=A[len-1-i];
C.push_back(t1);
D.push_back(t2);
}
for(int j=0;j<len;j++)
B.push_back(C[j]*D[len-1-j]);
return B;
}
};
进行代码优化：//不用再分配C,D的空间，节省了空间
class Solution {
public:
vector<int> multiply(const vector<int>& A) {
vector<int> B;
int len = A.size();
int tem=1;
if(len==0)
return B;
B.push_back(tem);
for(int i=0;i<len-1;i++){
tem*=A[i];
B.push_back(tem);
}
tem=1;
for(int j=len-2;j>=0;j--){
tem*=A[j+1];
B[j]*=tem;
}
return B;
}
};
| 
转播
