这一题一开始想到是用HashSet+链表来做，链表记录prev和next。这样也可以，后来看到都是连续的整数，而且交流了一下觉得可以用类似并查集的方式来做，一个数组，每个位置记录该位置的直接后继，删除元素时更改后继。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
vector<int> vec;
void
init(int
N) {
vec.resize(N);
for
(int
i = 0; i < N; i++) {
vec[i] = i;
}
}void
removeNum(int
x) {
if
(x >= vec.size()) return;
vec[x] = query(x+1);
}int
query(int
x) {
if
(x >= vec.size()) return
-1;
if
(vec[x] == x || vec[x] == -1) {
return
vec[x];
}
int
next = query(vec[x]);
vec[x] = next;
return
next;
} |