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

Question

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

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

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

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)方法对应于A中的x。 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 with 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)

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

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