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

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

假定L是没有重复的整数列表，则可以推断出，当且仅当L[index] == L[start] + (index - start)且仅当且仅当且仅当且仅当且仅当且仅当且仅当和时，列表的开始和索引之间的部分是完全连续的L[index] == L[end] - (end - index)。这与将列表一分为二地递归给出了一个次线性的解决方案。

# python 3.3 and up, in older versions, replace "yield from" with yield loop

def missing_elements(L, start, end):
    if end - start <= 1: 
        if L[end] - L[start] > 1:
            yield from range(L[start] + 1, L[end])
        return

    index = start + (end - start) // 2

    # is the lower half consecutive?
    consecutive_low =  L[index] == L[start] + (index - start)
    if not consecutive_low:
        yield from missing_elements(L, start, index)

    # is the upper part consecutive?
    consecutive_high =  L[index] == L[end] - (end - index)
    if not consecutive_high:
        yield from missing_elements(L, index, end)

def main():
    L = [10,11,13,14,15,16,17,18,20]
    print(list(missing_elements(L,0,len(L)-1)))
    L = range(10, 21)
    print(list(missing_elements(L,0,len(L)-1)))

main()