如何高效计算集合的最小不可达数（Minimum Excludant，Mex）

本文详解最小不可达数（Mex）的概念与实现，重点讲解基于集合查找的Python高效算法，纠正常见语法错误，并提供可直接运行的完整代码及边界情况处理建议。

本文详解最小不可达数（Mex）的概念与实现，重点讲解基于集合查找的Python高效算法，纠正常见语法错误，并提供可直接运行的完整代码及边界情况处理建议。

最小不可达数（Minimum Excludant，简称 Mex）是组合博弈论和算法竞赛中的基础概念：给定一个非负整数集合 $ S $，Mex 定义为不属于 $ S $ 的最小非负整数。例如，$ \text{Mex}({0,1,2,4}) = 3 $，因为 0、1、2 存在，3 缺失；而 $ \text{Mex}({1,2,3}) = 0 $，因为 0 是首个未出现的非负整数。

✅ 正确实现原理

核心思路简洁高效：

SnapEdit

AI移除图片中的任何物体

• 将输入列表转为 set，实现 $ O(1) $ 成员检查；
• 从 mex = 0 开始递增，首次遇到 mex not in set 即返回该值；
• 时间复杂度最坏为 $ O(n + k) $（$ k $ 为 Mex 值），空间复杂度 $ O(n) $，适用于绝大多数实际场景。

以下是修正后的标准实现（已修复原始代码中的缩进与冒号语法错误）：

def mex(my_list):
    s = set(my_list)  # 转换为集合，提升查找效率
    mex_val = 0
    while mex_val in s:  # 注意：冒号不可省略，且 return 必须与 while 对齐（在循环外）
        mex_val += 1
    return mex_val  # ✅ 正确缩进位置：与 while 同级

# 测试用例
print(mex([1, 0, 2, 4]))   # 输出: 3
print(mex([1, 2, 3]))      # 输出: 0
print(mex([0, 1, 2, 3]))   # 输出: 4
print(mex([]))             # 输出: 0（空集的 Mex 为 0）

⚠️ 常见错误与注意事项

• 语法陷阱：原始代码中 return mex 若缩进至 while 内部，将导致函数在第一次检查后立即退出（返回 0 或 1），逻辑完全失效；同时 while 语句末尾缺失 : 会引发 SyntaxError。
• 数据类型安全：确保输入仅含非负整数。若存在负数或非整型元素（如字符串、浮点数），mex_val in s 可能行为异常，建议增加输入校验：

  if not all(isinstance(x, int) and x >= 0 for x in my_list):
      raise ValueError("Input must contain only non-negative integers")

• 性能优化提示：对于极大规模或 Mex 值极大的场景（如 $ S = {0,1,2,\dots,10^6-1} $），可改用排序+单次扫描（$ O(n \log n) $），避免最坏 $ O(n + \text{Mex}) $ 的线性增长；但对一般用途，集合法更简洁鲁棒。

掌握 Mex 计算是理解 Nim 游戏、SG 函数等高级概念的第一步。本实现兼顾正确性、可读性与工程实用性，适合初学者快速上手并融入实际算法开发中。