本文详解最小不可达整数（minimum excludant，mex）的定义、python 实现原理及常见编码陷阱，提供健壮、可复用的实现方案，并强调语法细节与性能优化要点。
本文详解最小不可达整数（minimum excludant，mex）的定义、python 实现原理及常见编码陷阱，提供健壮、可复用的实现方案，并强调语法细节与性能优化要点。
最小不可达整数（MEX）是指不属于给定集合的最小非负整数。例如，集合 {0, 1, 2, 4} 的 MEX 是 3，因为 0、1、2 均存在，而 3 缺失；空集的 MEX 是 0；集合 {1, 2, 3} 的 MEX 同样是 0。
最直观且高效的实现方式是：将输入转换为集合（支持 O(1) 查找），然后从 0 开始递增检查，直到找到第一个不在集合中的整数。该算法时间复杂度为 O(n + k)，其中 k 是 MEX 值（通常远小于或等于 n+1），空间复杂度为 O(n)。
以下是推荐的 Python 实现：
def mex(my_list):
s = set(my_list) # 转换为集合，提升查找效率
candidate = 0
while candidate in s:
candidate += 1
return candidate
# 测试用例
print(mex([1, 0, 2, 4])) # 输出: 3
print(mex([])) # 输出: 0
print(mex([1, 2, 3])) # 输出: 0
print(mex([0, 1, 2, 3])) # 输出: 4⚠️ 关键注意事项：
- 缩进与语法：return 必须与 while 同级缩进（即在循环外），且 while 语句末尾必须有英文冒号 : —— 这是初学者最常见的语法错误（如原问题中缺失冒号或缩进错位会导致 SyntaxError）。
- 变量命名：避免用 mex 同时作为函数名和局部变量名（易引发混淆或意外覆盖），建议使用 candidate、result 等语义清晰的名称。
- 输入鲁棒性：上述实现默认输入为可迭代对象（如列表、元组）。若需处理含负数、浮点数或非整数元素的场景，应增加类型校验（例如 all(isinstance(x, int) and x >= 0 for x in my_list)），但标准 MEX 定义仅针对非负整数集合。
- 性能提示：对超大规模数据（如百万级稀疏数组），可考虑排序+单次遍历（O(n log n)）或位图（bit array）优化；但对一般场景，集合查找法简洁、高效且可读性强。
总结：MEX 是组合博弈论与算法竞赛中的基础概念，其 Python 实现虽简，却精准体现了“问题建模→数据结构选择→边界处理”的典型编程思维。掌握这一模式，有助于快速解决类似“首个缺失正整数”等变体问题。
