输入数组a1,a2,a3…
生成数组a2*a3, a1*a3, a1*a2，但是希望能够在O(n)的时间内解决，且不能使用除法。
用两个额外的数组记录ai前和ai后的乘积即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {
int size = nums.size();
vector<int> front(size), back(size), result(size);
front[0] = 1;
back[size-1] = 1;
for (int i = 1;i < size;i++)
{
front[i] = front[i-1] * nums[i-1];
}
for (int i = size - 2;i >= 0;i--)
{
back[i] = back[i + 1] * nums[i + 1];
}
result[0] = back[0];
result[size-1] = front[size - 1];
for (int i = 1;i < size - 1;i++)
{
result[i] = front[i] * back[i];
}
return result;
}
};
|