python - 在整数序列中查找缺失元素的有效方法

Question

假设我们在连续整数序列中缺少两个项目，并且缺少的元素位于第一个和最后一个元素之间。我确实编写了完成任务的代码。但是，如果可能的话，我想使用更少的循环来提高效率。任何帮助将不胜感激。另外，当我们必须找到更多缺失项(比如接近 n/4)而不是 2 个时，情况又如何呢？我认为我的代码应该是高效的，因为我较早地从循环中跳出？

def missing_elements(L,start,end,missing_num):
    complete_list = range(start,end+1)
    count = 0
    input_index = 0
    for item  in  complete_list:
        if item != L[input_index]:
            print item
            count += 1
        else :
            input_index += 1
        if count > missing_num:
            break



def main():
    L = [10,11,13,14,15,16,17,18,20]
    start = 10
    end = 20
    missing_elements(L,start,end,2)



if __name__ == "__main__":
    main()

Answer 1

如果输入序列是排序的，您可以在这里使用集合。从输入列表中获取起始值和结束值:

def missing_elements(L):
    start, end = L[0], L[-1]
    return sorted(set(range(start, end + 1)).difference(L))

这假设 Python 3；对于 Python 2，使用 xrange() 来避免首先构建列表。

sorted() 调用是可选的；没有它，返回缺失值的 set()，有了它，您将得到一个排序列表。

演示:

>>> L = [10,11,13,14,15,16,17,18,20]
>>> missing_elements(L)
[12, 19]

另一种方法是检测后续数字之间的差距；使用较旧的 itertools library sliding window recipe :

from itertools import islice, chain

def window(seq, n=2):
    "Returns a sliding window (of width n) over data from the iterable"
    "   s -> (s0,s1,...s[n-1]), (s1,s2,...,sn), ...                   "
    it = iter(seq)
    result = tuple(islice(it, n))
    if len(result) == n:
        yield result    
    for elem in it:
        result = result[1:] + (elem,)
        yield result

def missing_elements(L):
    missing = chain.from_iterable(range(x + 1, y) for x, y in window(L) if (y - x) > 1)
    return list(missing)

这是一个纯粹的 O(n) 操作，如果您知道缺失项的数量，您可以确保它只生成那些项然后停止:

def missing_elements(L, count):
    missing = chain.from_iterable(range(x + 1, y) for x, y in window(L) if (y - x) > 1)
    return list(islice(missing, 0, count))

这也将处理更大的间隙；如果您在 11 和 12 缺少 2 个项目，它仍然有效:

>>> missing_elements([10, 13, 14, 15], 2)
[11, 12]

上面的示例只需要遍历 [10, 13] 就可以解决这个问题。