查找 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

斯文的想法是正确的。您只需检查前面的数字 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 []

这仅对于作为输入的集合并且知道该集合仅包含整数而言始终是正确的。

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 []

它可能不是最有效的解决方案，但它很简洁。

编辑：贾斯汀的方法也可以变得更简洁：

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

应该可以了...在排序列表中向前查看 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 4

这是我想出的一个：

def smallest_contiguous(s,N):
    try:
        result = []
        while len(result) < N:
            min_value = min(s)
            s.remove(min_value)
            if result == [] or min_value == result[-1] + 1:
                result.append(min_value)
            else:
                result = [min_value]
        return result
    except ValueError:
        return []

它会修改输入集作为副作用。

Answer 5

itertools 来救援。 groupby 在这里完成所有繁重的工作
由于调用了 sorted()，该算法的复杂度为 O(n logn)

>>> from itertools import groupby, count
>>> def smallest_contiguous(s, N):
...     for i,j in groupby(sorted(s), key=lambda i,c=count().next: i-c()):
...         res = list(j)
...         if len(res) == N:
...             return res
...     return []

... 
>>> smallest_contiguous(s,5)
[40, 41, 42, 43, 44]
>>> smallest_contiguous(s,6)
[]

Answer 6

def smallest_contiguous(s, n):
    xs = sorted(s)
    return next(x for i, x in enumerate(xs) if xs[i + n - 1] == x + n - 1)