python - 有没有更有效的方法来找到丢失的整数？

Question

我目前正在大学学习一个名为数据结构和算法的模块。我们的任务是编写一种算法，找到在给定序列中不出现的最小正整数。我能够找到解决方案，但是否有更有效的方法？

x = [5, 6, 3, 1, 2]

def missing_integer():
    for i in range(1, 100):
        if i not in x:
            return i

print(missing_integer())

说明包括一些示例:
给定 x = [1, 3, 6, 4, 1, 2]，该函数应返回 5，
给定 x = [1, 2, 3]，该函数应返回 4 和
给定 x = [−1, −3]，该函数应返回 1。

Answer 1

你没有要求解决问题的最有效方法，只要有比你更有效的方法就好了。答案是是。

如果缺失的整数接近整数范围的顶部并且列表很长，则您的算法的运行时效率为 O(N**2)——您的循环遍历所有可能的值，如果未找到匹配项，则 not in 运算符会搜索整个列表。 (您的代码仅搜索值 100——我认为这只是您的错误，您希望处理任意长度的序列。)

这是一个简单的算法，其阶数仅为 O(N*log(N))。 (请注意，存在更快的算法——我展示了这个算法，因为它很简单，因此很容易回答您的问题。)对序列(具有我规定的顺序)进行排序，然后从最小值开始运行它。这种线性搜索很容易找到丢失的正整数。该算法的另一个优点是序列可以包含负数、非整数和重复数，并且代码可以轻松处理这些。这也可以处理任何大小的序列和任何大小的数字，当然对于更长的序列它运行的时间更长。如果使用良好的排序例程，内存使用量会非常小。