在Python集合中找到最小的连续整数

Question

在Python的集合中，获取最小的N个连续整数的最佳方法是什么？

>>> s=set([5,6,10,12,13,15,30,40,41,42,43,44,55,56,90,300,500])
>>> s
set([42, 43, 44, 5, 6, 90, 300, 30, 10, 12, 13, 55, 56, 15, 500, 40, 41])
>>> smallest_contiguous(s,5)
[40,41,42,43,44]
>>> smallest_contiguous(s,6)
[]

编辑：感谢大家的回答。

Answer 1

这样就可以了……在这个已经排好序的列表中，向前看 length - 1 步。因为这个列表只包含整数并且是排好序的，所以它们之间的差值也必须是 length - 1。

def smallest_contiguous(myset, length):
    if len(myset) < length:
        return []

    s = sorted(myset)
    for idx in range(0, len(myset) - length + 1):
        if s[idx+length-1] - s[idx] == length - 1:
            return s[idx:idx+length]

    return []

s=set([5,6,10,12,13,15,30,40,41,42,43,44,55,56,90,300,500])
print smallest_contiguous(s, 5)
print smallest_contiguous(s, 6)

Answer 2

这样怎么样？

def smallest_contiguous(s, N):
    lst = sorted(s)
    for i in lst:
        t = range(i, i+N)
        if s.issuperset(t):
            return t
    return []

这可能不是最有效的解决办法，但它很简洁。

补充一下：Justin的方法也可以变得更简洁：

def smallest_contiguous(s, N):
    lst = sorted(s)
    for a, b in zip(lst, lst[N - 1:]):
        if b - a == N - 1:
            return range(a, b + 1)
    return []

Answer 3

Sven的想法是对的。你可以通过只检查数字N减去1来避免检查超集。

def smallest_contiguous(s, N):
    lst = list(s)
    lst.sort()
    Nm = N-1
    for i in xrange(len(lst) - Nm):
        if lst[i] + Nm == lst[i + Nm]:
            return range(lst[i], lst[i]+N)
    return []

这样做只有在输入是一个集合，并且知道这个集合只包含整数时，才总是正确。