MEX：最小非负整数 - Blume's Skylog

归档38

数据结构与算法11 云原生与运维8 后端开发8 编程语言7 前端开发4

210 字

1 分钟

MEX：最小非负整数

2024-10-20

MEX 即一个数组中的最小非负整数，它满足下面三个性质：

只有在添加的数等于当前序列的mex时，mex的值才会变化。添加操作只会使得mex变大删除操作会使得mex的值变小。

Problem - C - Codeforces

对于一个随时插入，删除元素的数组，想高效的查询mex可使用 set 和一个计数数组

用一个set<int> st 来记录没有出现过的数，然后直接取最小值就可以了，当然需要一个cnt来计数。

最小值用begin取得

1
struct Mex {
2
    static const int N = 1e5 + 5;
3
    int cnt[N] = {};
4
    set<int> s;
5
    Mex() { for (int i = 0; i < N; ++i) s.insert(i); }
6

7
    void add(int x) {
8
        if (!cnt[x]) s.erase(x);
9
        ++cnt[x];
10
    }
11

12
    void del(int x) {
13
        if (cnt[x] == 1) s.insert(x);
14
        if (cnt[x]) --cnt[x];
15
    }
16

17
    int get() { return *s.begin(); }
18
};