题目描述
给定一个数组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]。不能使用除法。
1.题目要求新的数组中不能出现与自己下标i相同的A元素，而其他元素累积相乘。
2.我们通过构建一个前向乘积数组(A[0]*A[1]*…*A[i-1])和后向乘积数组(A[i+1]*A[i+2]*….A[n-1])，然后把两个数组相乘，即可获得所求数组B。
3.实际操作中，我们只需要新建一个结果数组即可，上面的累积乘积可以使用一个变量替代。
4.时间复杂度为O(n)，空间复杂度为O(n)。
AC代码如下：
[c language=”++”]
class Solution {
public:
vector<int> multiply(const vector<int>& A) {
vector<int> result(0);
if(A.size()==0)
return result;
result=vector<int>(A.size(),1);
int tmp=1;
//前向乘积数组
for(int i=1;i<A.size();++i)
{
tmp*=A[i-1];
result[i]*=tmp;
}
tmp=1;
//后向乘积数组
for(int i=A.size()-2;i>=0;–i)
{
tmp*=A[i+1];
result[i]*=tmp;
}
return result;
}
};
[/c]