在整数序列中查找缺失元素的有效方法 [英] Efficient way to find missing elements in an integer sequence

问题描述

假设我们在一系列连续整数中缺少两个项目，缺少的元素位于第一个和最后一个元素之间。我写了一个完成任务的代码。但是，如果可能的话，我希望使用更少的循环来提高效率。任何帮助将不胜感激。当我们必须找到更多缺失的项目（比如接近n / 4）而不是2时，情况怎么样呢？我认为我的代码应该是高效的，因为我早先从循环中突然出现了？

Suppose we have two items missing in a sequence of consecutive integers and the missing elements lie between the first and last elements. I did write a code that does accomplish the task. However, I wanted to make it efficient using less loops if possible. Any help will be appreciated. Also what about the condition when we have to find more missing items (say close to n/4) instead of 2. I think then my code should be efficient right because I am breaking out from the loop earlier?

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

推荐答案

假设L是一个没有重复的整数列表，你可以推断，当且仅当 L [index] == L [start] +时，start和index之间的列表部分是完全连续的（index - start）和index类似，当且仅当 L [index] == L [end] - （end - index）。这与将列表分成两个递归地结合起来给出了一个次线性解决方案。

Assuming that L is a list of integers with no duplicates, you can infer that the part of the list between start and index is completely consecutive if and only if L[index] == L[start] + (index - start) and similarly with index and end is completely consecutive if and only if L[index] == L[end] - (end - index). This combined with splitting the list into two recursively gives a sublinear solution.

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

这篇关于在整数序列中查找缺失元素的有效方法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！