动态集合的MEX求解：add方法效率优化咨询

你的两种实现效率低的核心原因是每次添加元素后都要从头遍历查找MEX，最坏情况下每次操作的时间复杂度是O(n)，当添加大量元素时性能会急剧下降。

优化方案：维护当前MEX值 #

不需要每次从头遍历，而是在类中维护一个current_mex变量，记录当前已知的最小非负缺失值。每次添加元素时，仅在必要时更新这个值，摊还时间复杂度可以做到O(1)。

优化后的代码：

class Mex:
    def __init__(self):
        self.elements = set()
        self.current_mex = 0

    def add(self, x):
        self.elements.add(x)
        # 只有当添加的元素恰好是当前维护的MEX时，才需要向后查找新的MEX
        while self.current_mex in self.elements:
            self.current_mex += 1
        return self.current_mex

优化原理 #

• current_mex初始为0，只会递增不会减小，因为已经出现过的非负整数不会凭空消失。
• 只有当添加的元素正好等于current_mex时，才需要进入循环查找下一个缺失值，每个元素最多触发一次current_mex的递增操作，总操作次数等于添加的元素总数，因此整体摊还时间复杂度为O(1)。
• 集合elements用于快速判断某个数是否存在，查找操作是O(1)。

这种方式避免了每次添加元素后都从头遍历的开销，在处理大量元素时性能会有显著提升。

内容的提问来源于stack exchange，提问作者user17438591