algorithm - 查找最小排除项 ( MEX )

Question

我正在寻找一种算法来找到 mex但除了这个 wiki 链接，找不到任何有用的东西。
看完后我拉出这段代码:

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

您的代码的问题在于，不能保证集合上的迭代顺序为递增顺序，因此您的原始代码有时可能会返回错误的答案。

你的测试用例没有打开它的原因是因为我相信 Python 3 目前将整数散列到它们的值模一个大质数(可以在 sys.hash_info.modulus 中读取)，然后从基于列表的列表构造集合按哈希值排序。实际上，这意味着对于正常大小的整数，您的集合将按顺序返回值，因此您的代码可以工作(但可能不会在 Python 3 的 future 或替代实现中)。