Эффективный способ поиска отсутствующих элементов в целочисленной последовательности

Ответ 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()

Ответ 2

Если последовательность ввода сортируется, вы можете использовать здесь. Возьмите начальные и конечные значения из списка ввода:

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

Это позволит справиться с большими пробелами; если вам не хватает 2 предметов в 11 и 12, он все равно будет работать:

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

и вышеприведенный образец должен был перебирать более [10, 13], чтобы понять это.

Ответ 3

missingItems = [x for x in complete_list if not x in L]

Ответ 4

Используя collections.Counter:

from collections import Counter

dic = Counter([10, 11, 13, 14, 15, 16, 17, 18, 20])
print([i for i in range(10, 20) if dic[i] == 0])

Вывод:

[12, 19]

Ответ 5

Использование scipy lib:

import math
from scipy.optimize import fsolve

def mullist(a):
    mul = 1
    for i in a:
        mul = mul*i
    return mul

a = [1,2,3,4,5,6,9,10]
s = sum(a)
so = sum(range(1,11))
mulo = mullist(range(1,11))
mul = mullist(a)
over = mulo/mul
delta = so -s
# y = so - s -x
# xy = mulo/mul
def func(x):
    return (so -s -x)*x-over

print int(round(fsolve(func, 0))), int(round(delta - fsolve(func, 0)))

Сроки:

$ python -mtimeit -s "$(cat with_scipy.py)" 

7 8

100000000 loops, best of 3: 0.0181 usec per loop

Другой вариант:

>>> from sets import Set
>>> a = Set(range(1,11))
>>> b = Set([1,2,3,4,5,6,9,10])
>>> a-b
Set([8, 7])

И время:

Set([8, 7])
100000000 loops, best of 3: 0.0178 usec per loop

Ответ 6

Здесь однострочный:

In [10]: l = [10,11,13,14,15,16,17,18,20]

In [11]: [i for i, (n1, n2) in enumerate(zip(l[:-1], l[1:])) if n1 + 1 != n2]
Out[11]: [1, 7]

Я использую список, нарезая для смещения копий на единицу и использую перечисление для получения индексов отсутствующего элемента.

Для длинных списков это не очень удобно, потому что это не O (log (n)), но я думаю, что это должно быть довольно эффективно против использования set для небольших входов. izip из itertools, вероятно, сделает это еще быстрее.

Ответ 7

Мое занятие состояло в том, чтобы не использовать циклы и задавать операции:

def find_missing(in_list):
    complete_set = set(range(in_list[0], in_list[-1] + 1))
    return complete_set - set(in_list)

def main():
    sample = [10, 11, 13, 14, 15, 16, 17, 18, 20]
    print find_missing(sample)

if __name__ == "__main__":
    main()

# => set([19, 12])

Ответ 8

Просто пройдите по списку и найдите номера, не соответствующие последовательностям:

prev = L[0]
for this in L[1:]:
    if this > prev+1:
        for item in range(prev+1, this):    # this handles gaps of 1 or more
            print item
    prev = this

Ответ 9

Мы обнаружили недостающее значение, если разница между двумя последовательными номерами больше, чем 1:

>>> L = [10,11,13,14,15,16,17,18,20]
>>> [x + 1 for x, y in zip(L[:-1], L[1:]) if y - x > 1]
[12, 19]

Примечание: Python 3. В Python 2 используйте itertools.izip.

Улучшенная версия для нескольких значений, отсутствующих в строке:

>>> import itertools as it
>>> L = [10,11,14,15,16,17,18,20] # 12, 13 and 19 missing
>>> [x + diff for x, y in zip(it.islice(L, None, len(L) - 1),
                              it.islice(L, 1, None)) 
     for diff in range(1, y - x) if diff]
[12, 13, 19]

Ответ 10

>>> l = [10,11,13,14,15,16,17,18,20]
>>> [l[i]+1 for i, j in enumerate(l) if (l+[0])[i+1] - l[i] > 1]
[12, 19]

Ответ 11

def missing_elements(inlist):
    if len(inlist) <= 1:
        return []
    else:
        if inlist[1]-inlist[0] > 1:
            return [inlist[0]+1] + missing_elements([inlist[0]+1] + inlist[1:])
        else:
            return missing_elements(inlist[1:])

Ответ 12

Сначала мы должны отсортировать список, а затем проверить каждый элемент, кроме последнего, если следующее значение находится в списке. Будьте осторожны, чтобы не было дубликатов в списке!

l.sort()

[l[i]+1 for i in range(len(l)-1) if l[i]+1 not in l]

Ответ 13

a = [1, 2, 5, 6, 10, 12]
diff = []

for i in range(a[0], len(a) - 1):
    val = a[i]
    val_next = a[i + 1]

    if val + 1 != val_next:
        diff.extend(range(val + 1, val_next))

print(diff)

>> [3, 4, 7, 8, 9, 11]

Если список отсортирован, мы можем найти любой пробел. Затем создайте объект диапазона между текущим (+1) и следующим значением (не включительно) и добавьте его в список различий.

Ответ 14

С помощью этого кода вы можете найти любые пропущенные значения в последовательности, кроме последнего числа. Требуется только ввести ваши данные в файл Excel с именем столбца "числа".

import pandas as pd
import numpy as np

data = pd.read_excel("numbers.xlsx")

data_sort=data.sort_values('numbers',ascending=True)
index=list(range(len(data_sort)))
data_sort['index']=index
data_sort['index']=data_sort['index']+1
missing=[]

for i in range (len(data_sort)-1):
    if data_sort['numbers'].iloc[i+1]-data_sort['numbers'].iloc[i]>1:
        gap=data_sort['numbers'].iloc[i+1]-data_sort['numbers'].iloc[i]
        numerator=1
        for j in range (1,gap):          
            mis_value=data_sort['numbers'].iloc[i+1]-numerator
            missing.append(mis_value)
            numerator=numerator+1
print(np.sort(missing))