查找最小排除项 ( MEX )

Question

我正在寻找一种算法来找到 mex，但除了这个 wiki link 之外找不到任何有用的东西。
读完后我提取了这段代码：

nList = [int(x) for x in input().split()]
nList = set(nList)
mex = 0
for i in nList:
    if i<=mex:
        mex += 1
if mex == max(nList):
    print(mex+1)
else:
    print(mex)

所以它是正确的吗？我尝试过的任何测试用例似乎都有效，如果没有请指导我。
就时间复杂度而言，这是最好的方法吗？
代码在 python3 抱歉。

Answer 1

我通常将 mex 函数编码为：

nList = set(nList)
mex = 0
while mex in nList:
  mex += 1

您的代码存在的问题是不能保证集合的迭代顺序是递增顺序，因此您的原始代码有时可能 return 错误答案。

你的测试用例没有打开它的原因是因为我相信 Python 3 当前将整数散列到它们的值模一个大质数（可以在 sys.hash_info.modulus 中读取），并且然后根据哈希值排序从列表构造集合。实际上，这意味着对于正常大小的整数，您的集合将按顺序 return 值，因此您的代码有效（但可能不适用于 Python 3 的未来或替代实现）。

查找最小排除项 ( MEX )

Find Minimum excludant ( MEX )

algorithm

set

game-theory