动态正整数MEX：find、fill、delete与扫描成本

题目重点：维护集合里缺失的最小正整数，删除会让答案往回退。

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

重复add幂等；remove不存在项不报错；fill取当前MEX并插入，然后返回该值。
find为单线程即时查询；只接受正整数，删除的目标也应来自正整数域。

解题路线

保持missing为最小不在集合的正整数。插入x后，只在missing被占时向前扫描直到空缺；其他插入不会改变答案。
删除现存x后，新的MEX=min(oldMissing,x)，因为比二者更小的数仍全部存在。find直接返回missing。
无删除时missing只递增，可摊还计扫描；有删除时反复remove(1)/add(1)会每次扫长前缀，不能声称所有更新摊还O(1)。大规模动态合同需有序缺口区间/树状结构。

手动走一遍

add1,add3后MEX2；fill返回2并把MEX推进4；remove1后MEX1。集合1..N反复删1再加1，每次add扫描到N+1，揭示最坏成本。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

class MexSet:
    def __init__(self):
        self.values = set()
        self.missing = 1

    def add(self, x):
        if type(x) is not int or x < 1:
            raise ValueError("positive integer required")
        self.values.add(x)
        while self.missing in self.values:
            self.missing += 1

    def remove(self, x):
        if x in self.values:
            self.values.remove(x)
            self.missing = min(self.missing, x)

    def find(self):
        return self.missing

    def fill(self):
        answer = self.missing
        self.add(answer)
        return answer

复杂度

find期望/实际O(1)读取；remove期望O(1)；add/fill最坏O(M)连续扫描，集合空间O(n)。哈希访问平均常数但不能消掉扫描长度。

易错点与追问

容易失分的边界

MEX从1开始，0不参与。
仅用minheap保存所有删除值还需去除已重新加入的stale值，并处理尚未分配的尾部。

继续深挖

若所有值≤U，segment tree怎样找第一个零计数位？
需要线程安全时fill的读和插入应怎样原子化？