找到不在列表中的最小正数

Question

我在 python 中有一个这样的列表：

 myList = [1,14,2,5,3,7,8,12]

如何轻松找到第一个未使用的值？ （在本例中为“4”）

原文由 jul 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

我想出了几种不同的方法：

迭代第一个不在集合中的数字

我不想获得最短的代码（这可能是设置差异的诡计），而是一些可以有良好运行时间的代码。

这可能是这里最好的建议之一，我的测试表明它可能比集合差异方法快得多 - 特别是如果洞在开始时 - ：

 from itertools import count, filterfalse # ifilterfalse on py2

A = [1,14,2,5,3,7,8,12]
print(next(filterfalse(set(A).__contains__, count(1))))

该数组变成了 set ，其 __contains__(x) 方法对应于 x in A 。 count(1) 创建一个从 1 开始计数到无穷大的计数器。现在， filterfalse 消耗计数器中的数字，直到找到不在集合中的数字；当找到第一个不在集合中的数字时，它由 next() 产生

时间 len(a) = 100000 ，随机和抢手的数字是 8 ：

 >>> timeit(lambda: next(filterfalse(set(a).__contains__, count(1))), number=100)
0.9200698399945395
>>> timeit(lambda: min(set(range(1, len(a) + 2)) - set(a)), number=100)
3.1420603669976117

时间为 len(a) = 100000 ，订购和第一个免费的是 100001

 >>> timeit(lambda: next(filterfalse(set(a).__contains__, count(1))), number=100)
1.520096342996112
>>> timeit(lambda: min(set(range(1, len(a) + 2)) - set(a)), number=100)
1.987783643999137

（请注意，这是 Python 3 和 range 是 py2 xrange ）

使用heapq

渐近的好答案： heapq 与 enumerate

 from heapq import heapify, heappop

heap = list(A)
heapify(heap)

from heapq import heapify, heappop
from functools import partial

# A = [1,2,3] also works
A = [1,14,2,5,3,7,8,12]

end = 2 ** 61      # these are different and neither of them can be the
sentinel = 2 ** 62 # first gap (unless you have 2^64 bytes of memory).

heap = list(A)
heap.append(end)
heapify(heap)

print(next(n for n, v in enumerate(
     iter(partial(heappop, heap), sentinel), 1) if n != v))

现在，如果用 C 编写，上面的解决方案可能是首选解决方案，但是 heapq 是用 Python 编写的，很可能比许多其他主要使用 C 代码的替代方案慢。

只需排序和枚举即可找到第一个不匹配的

或具有 O(n lg n) 良好常数的简单答案

next(i for i, e in enumerate(sorted(A) + [ None ], 1) if i != e)

如果 由于 Python Timsort 的工作方式，列表几乎已排序，这可能是最快的，但对于随机化，集合差异和迭代第一个不在集合中的速度更快。

+ [ None ] 对于没有间隙的边缘情况是必需的（例如 [1,2,3] ）。

原文由 Antti Haapala – Слава Україні 发布，翻译遵循 CC BY-SA 3.0 许可协议

Answer 2

这利用了集合的属性

>>> l = [1,2,3,5,7,8,12,14]
>>> m = range(1,len(l))
>>> min(set(m)-set(l))
4

原文由 Bhargav Rao 发布，翻译遵循 CC BY-SA 3.0 许可协议