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

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库滑动窗口配方:

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]来计算出来.

Answer 2

假设L是一个没有重复的整数列表,你可以推断出start和index之间列表的部分是完全连续的,当且仅当L[index] == L[start] + (index - start)index和end是完全连续时,当且仅当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()