1.暴力法
每次计算除当前元素之外所有元素的乘积
class Solution { public: vector<int> multiply(const vector<int>& A) { vector<int>B(A.size(), 0); for(int i=0;i<A.size();i++){ int tmp=1; for(int j=0;j<A.size();j++){ if(j!=i){ tmp*=A[j]; } } B[i]=tmp; } return B; } };
2.缓存乘积结果
因为对于i位置的乘积我们发现取决于i之前的元素乘积 * i之后的元素乘积,那么我们就可以分别用数组预先计算前向和后向的乘积
class Solution { public: vector<int> multiply(const vector<int>& A) { vector<int>forward(A.size(), 0); vector<int>backward(A.size(), 0); forward[0]=A[0]; for(int i=1;i<A.size();i++){ forward[i]=forward[i-1]*A[i]; } backward[A.size()-1]=A[A.size()-1]; for(int i=A.size()-2;i>=0;i--){ backward[i]=backward[i+1]*A[i]; } vector<int>B(A.size(), 0); for(int i=0;i<A.size();i++){ if(i==0) B[i]=backward[i+1]; else if(i==A.size()-1) B[i]=forward[i-1]; else{ B[i]=backward[i+1]*forward[i-1]; } } return B; } };