时间限制：1秒空间限制：32768K热度指数：5159
本题知识点：数组
**算法知识视频讲解
题目描述
给定一个数组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]。不能使用除法。
代码如下：
第一种low方法
class Solution {
public:
vector<int> multiply(const vector<int>& A) {
int size=A.size();
vector<int>b(size,1);
for(int i=0;i<size;++i){
for(int j=0;j<size;++j){
if(i!=j)b[i]*=A[j];
}
}
return b;
}
};
第二种时间复杂度为O（n）的方法
class Solution {
public:
vector<int> multiply(const vector<int>& A) {
int size=A.size();
vector<int>b(size);
vector<int>pre(size),back(size);
pre[0]=1;back[0]=1;
for(int i=1;i<size;++i){
pre[i]=A[i-1]*pre[i-1];
back[i]=back[i-1]*A[size-i];
}
for(int i=0;i<size;++i){
b[i]=pre[i]*back[size-i-1];
}
return b;
}
};
