本文详解python中计算最小未出现非负整数（minimum excludant, mex）的正确实现方法，涵盖基础逻辑、常见语法错误规避、时间复杂度分析及实用优化技巧。
本文详解python中计算最小未出现非负整数（minimum excludant, mex）的正确实现方法，涵盖基础逻辑、常见语法错误规避、时间复杂度分析及实用优化技巧。
最小未出现非负整数（Minimum Excludant，简称 MEX）是组合博弈论与算法竞赛中的经典概念：给定一个非负整数集合（或列表），MEX 是不在该集合中最小的非负整数。例如，[0, 1, 2, 4] 的 MEX 是 3；[1, 2, 3] 的 MEX 是 0；[0, 1, 3, 4] 的 MEX 是 2。
✅ 正确实现：简洁、健壮、高效
最直观且推荐的实现方式是将输入转为集合（set）以支持 O(1) 成员检查，然后从 0 开始递增遍历，直到找到第一个不在集合中的数：
def mex(my_list):
s = set(my_list) # 去重并加速查找
mex_val = 0
while mex_val in s:
mex_val += 1
return mex_val # 注意：return 必须与 while 同级缩进，且 while 后需有冒号 ':'
# 测试用例
print(mex([1, 0, 2, 4])) # 输出: 3
print(mex([1, 2, 3])) # 输出: 0
print(mex([0, 1, 3, 4])) # 输出: 2
print(mex([])) # 输出: 0（空集的 MEX 定义为 0）⚠️ 关键语法提醒（新手易错点）：
- while 语句末尾必须加英文冒号 :，否则触发 SyntaxError；
- return 语句不可缩进至 while 块内（否则循环仅执行一次即返回），应与 while 保持相同缩进层级；
- 变量命名避免覆盖内置名（如原代码中用 mex 作变量名虽可行，但易混淆，建议改用 mex_val 等清晰标识）。
? 时间复杂度与适用场景分析
- 时间复杂度：O(n + k)，其中 n 是输入长度，k 是 MEX 值（最坏情况 k ≈ n，如 [0,1,2,...,n-1] 时 MEX = n）；
- 空间复杂度：O(n)，用于存储集合；
- 该方法适用于一般规模数据（≤ 10⁵ 元素），代码简洁、可读性强，是教学与工程实践的首选。
? 进阶优化（可选）
若需处理超大数组或频繁调用场景，可考虑以下优化：
- 提前剪枝：若已知最大可能 MEX 上界（如题目限定所有数 ∈ [0, N]），可将循环上限设为 len(my_list) + 1，避免无限等待；
-
排序+单次扫描（适合已排序或允许排序的场景）：
def mex_sorted(arr): if not arr or arr[0] > 0: return 0 for i, x in enumerate(arr): if x != i: return i return len(arr)
✅ 总结
计算 MEX 的核心在于理解其定义——“从 0 开始找第一个缺失的非负整数”。使用 set 提升查找效率、严格遵循 Python 缩进与语法规范，即可写出正确、高效、易维护的实现。对于初学者，务必重视冒号与缩进这两个看似微小却决定成败的语法细节；对进阶用户，可根据数据特征选择更优策略。掌握 MEX 不仅是解决特定问题的关键，更是训练逻辑严谨性与算法直觉的重要一课。
