CodingInterview-构建乘积数组

参考了书中的思路,解法非常巧妙。将乘法分为两半,一半是A[0]*A[1]*...*A[i-1],另一半是A[i+1]*A[i+2]*...*A[n-1]。这两半可以分别从左边和右边算起。从左边开始算的时候,只要保证result[i]是它的前一个值和 A 的前一个值相乘即可。而从右边算起的时候,只要保证是后一个值得累乘就可以了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
vector<int> multiply(const vector<int>& A) {
vector<int> result;
int length=A.size();
if(length<=0) return result;
result.push_back(1);
for(int i=1;i<length;i++){
result.push_back(result[i-1]*A[i-1]);
}
int temp=1;
for(int i=length-1;i>=0;i--){
result[i]*=temp;
temp*=A[i];
}
return result;
}
};