在算法与数据结构领域，最小不可达整数（MEX）是一个基础但容易被低估的概念。它描述的是：对于一个包含非负整数的集合，找出最小的、不在该集合中的非负整数。比如集合包含0、1、2，那么MEX就是3；如果集合是1、2、3，MEX则是0。这个看似简单的计算，在频繁更新的场景下如果处理不当，会成为性能瓶颈。
暴力遍历方法的原理与局限
最直观的思路是从0开始逐个检查每个整数是否出现在集合中，直到找到第一个缺失的数。这种方法不需要任何预处理，代码写起来也非常直接，适合数据量极小或者只计算一次的场景。在教学的语境里，它清晰地表达了MEX的定义，初学者一眼就能看懂逻辑。
不过，当集合规模达到十万甚至更大时，这种方法的弱点就暴露出来了。假设集合中恰好包含了从0到n-1的所有数，那么我们必须检查n次才能确认MEX是n。如果每次检查都要在数组或列表里线性搜索，整体复杂度会变为O(n^2)。即便用哈希结构加速查找，遍历本身也是O(n)，在需要反复求解MEX的循环里依然累积出可观开销。
下面是一段典型的暴力实现，用列表存储集合元素，每次从0向上试：
def mex_bruteforce(arr):
# arr为输入的非负整数列表
i = 0
while True:
if i not in arr:
return i
i += 1
# 示例
print(mex_bruteforce([0, 1, 2, 4])) # 输出3
这段代码中 i not in arr 在Python列表上是线性扫描，若arr很长就会很慢。即便换成集合传入，虽然查找变快，但while循环仍要递增试探，无法跳过连续区间。
哈希表标记法的高效实现
为了把查找步骤降到近似常数时间，我们可以先将集合中的所有元素放入哈希表（如Python的set或Java的HashSet），然后同样从0开始递增，利用哈希表的O(1)成员判断来快速跳过存在的数。由于MEX的值不会超过集合元素个数加一，循环最多执行n+1次，整体时间复杂度是O(n)，空间复杂度也是O(n)。
这种写法在单次计算、集合静态不变的场景里几乎是最优解。它兼顾了代码简洁与执行效率，而且不需要改动原数据顺序。需要注意的是，如果集合里含有负数或大整数，应当先过滤或忽略，因为MEX的定义限定在非负整数范围，负数不参与比较。
以下示例展示了用集合优化的版本：
def mex_hash(arr):
s = set(arr)
i = 0
while i in s:
i += 1
return i
# 示例
print(mex_hash([3, 0, 1, 5])) # 输出2
这里 set(arr) 一次性建立哈希索引，之后 i in s 是平均O(1)的操作。当数组长度为n时，函数很快就能定位MEX，不会像暴力法那样在列表里反复扫描。
如果语言不支持原生集合，也可以用布尔数组来标记。开辟一个长度为n+1的数组，把出现的元素对应下标置为True，再从0扫到n+1找第一个False。这种做法在数值范围紧凑时比哈希表更省内存碎片，但要求提前知道或估算n的上界。
动态集合下的线段树维护方案
在博弈游戏模拟或滑动窗口统计中，集合经常插入和删除元素，此时每次重新算MEX都会重复劳动。线段树可以帮助我们维护“每个非负整数区间是否已被完全覆盖”，从而在修改操作后快速得知最小未覆盖点。叶子节点代表单个数字的存在状态，内部节点记录子树是否全满。
具体地说，每个叶子初始化为0（不存在），插入x就把位置x置1，删除则置0，随后自底向上更新：如果左子树和右子树都满，则父节点满。查询MEX时从根节点出发，若左子区间未满则递归左子，否则递归右子，直到叶子。这样单点更新和查询都是O(log n)，远胜于动态重建哈希表。
示例伪代码描述线段树查询逻辑：
// 假设seg_tree为完全二叉树数组，节点存区间是否全满
int query_mex(int node, int l, int r) {
if (l == r) {
return l; // 找到首个未覆盖叶子
}
int mid = (l + r) / 2;
if (!seg_tree[node * 2]) {
return query_mex(node * 2, l, mid);
} else {
return query_mex(node * 2 + 1, mid + 1, r);
}
}
上述过程要求线段树规模覆盖可能的最大MEX值。实际工程中可设定上限如二十万，避免无限扩张。相比每次重算，线段树把高频更新下的均摊成本压到极低，是大规模动态场景的可靠选择。
除了线段树，使用带秩的平衡树（如Treap）按升序保存存在的数字，也能通过找前驱后继的空隙算MEX，但实现复杂度更高。团队应根据维护频率、数值范围和开发成本权衡，不必盲目追求高级结构。
实际工程中的选型建议
面对MEX计算需求，第一步应明确集合是否动态变化。若只是离线批处理，哈希或布尔数组已足够，引入复杂结构反而增加bug概率。许多线上统计任务每天跑一次，用简单脚本就能在毫秒级完成。
当业务出现实时博弈状态推演、持续流入的日志去重计数等，才需要考虑线段树或分块。此时还要评估数值稀疏度：若实际出现的数字集中在很小区间，布尔数组配合原子操作可能比线段树更轻量。另外在多线程环境，更新和查询的锁粒度也影响整体吞吐，不能仅看算法大O。
最后提醒，无论采用哪种方案，都要在单元测试里覆盖边界，例如空集合MEX为0、连续前缀缺失、超大跳跃数值等。只有把定义和场景对齐，才能写出既快又正确的MEX计算模块。