Given an input array a1, a2, a3, …
Generate an output array where each element is the product of all other elements, e.g. a2a3, a1a3, a1*a2. The goal is to solve it in O(n) time without using division.
Use two extra arrays to store the prefix product and suffix product for each index.
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;
}
};
|