- 给定一个数组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[0] = A[1] * A[2] * ... * A[n-1],B[n-1] = A[0] * A[1] * ... * A[n-2];)
- B[i] 可分为两部分相乘:A[0, i-1] 和 A[i, n-1]
- 可分别计算这两者,分别存到两个数组中
- 优化:只记录一个数组,另个一个叠乘即可
- C++ 代码:
class Solution {
public:
vector<int> multiply(const vector<int>& A) {
if(A.empty()) return {};
vector<int> res(A.size(),1);
int i = 0;
int j = A.size()-1;
while(i<A.size()){
if(i!=0)
res[i] = A[i-1]*res[i-1];
i++;
}
int tmp = 1;
while(j>=0){
if(j!= (A.size()-1)){
tmp = tmp*A[j+1];
res[j] *= tmp;
}
j--;
}
return res;
}
};
网友评论