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

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))))

该数组变为a 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]).

Answer 2

这利用了集合的属性

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

Answer 3

使用列表的 for 循环即可完成此操作。

l = [1,14,2,5,3,7,8,12]
for i in range(1, max(l)):
    if i not in  l: break
print(i) # result 4

Answer 4

我建议您使用生成器并使用枚举来确定缺少的元素

>>> next(a for a, b in enumerate(myList, myList[0]) if a != b)
4

枚举将索引与元素进行映射，因此您的目标是确定与其索引不同的元素。请注意，我还假设元素可能不是以确定的值开头，在这种情况下为1，如果是这样，则可以进一步简化表达式，如下所示：

>>> next(a for a, b in enumerate(myList, 1) if a != b)
4

Answer 5

不知道效率如何，但是为什么不使用xrange作为掩码并使用set minus？

>>> myList = [1,14,2,5,3,7,8,12]
>>> min(set(xrange(1, len(myList) + 1)) - set(myList))
4

您只创建了一个与一样大的集合myList，所以它不会那么糟:)

这不适用于“完整”列表：

>>> myList = range(1, 5)
>>> min(set(xrange(1, len(myList) + 1)) - set(myList))
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
ValueError: min() arg is an empty sequence

但是返回下一个值的解决方法很简单（将另外一个值添加到掩码集中）：

>>> min(set(xrange(1, len(myList) + 2)) - set(myList))
5