Поиск отсутствующих элементов среди ряда числовых строк

Question

Скажем, у меня есть список диапазонов (то есть [[1,100][102, 200], etc]] я хочу найти количество недостающих элементов в общем диапазоне У меня есть алгоритм работы ниже:

def missing(numranges): 
    (minimum, maximum) = (min(map(lambda x: x[0], numranges)), 
          max(map(lambda x: x[1], numranges))) 
    (count, i) = (0, minimum) 

    while i < maximum: 
     if any(j <= i <= k for j, k in numranges): 
      count += 1 
     i += 1 

return maximum - minimum - count 

Проблема заключается в том, что вы сказали, что номер строки, который говорит, как [[1, 10000], [10002, 20000]], тогда я просматриваю все 20 000 элементов, и мне кажется, что это очень неэффективно. Я пытаюсь найти способ улучшить алгоритм но я немного в тупике.

Редактировать: К сожалению, следовало бы упомянуть, что диапазоны чисел могут перекрываться (то есть [1, 10000], [1, 100001], [100003, 100005], etc]]

Answer 1

Смотреть этот код

l=[[1, 50], [55, 90], [95, 100]] 
res=[] 
for item in l : 
    res.extend(range(item[0],item[1])) 
print [k for k in range(max(res)) if k not in res] 

Выход:

[0, 50, 51, 52, 53, 54, 90, 91, 92, 93, 94] 

Answer 2

Здесь я предполагаю, основываясь на вашем примере, что список находится в порядке возрастания и ваши диапазоны не будут перекрываться

>>> l = [[1, 50] ,[55, 90], [95, 100]] 
>>> sum([l[i+1][0]-m[1]-1 for i, m in enumerate(l[:-1])]) 
8 

Логик: Я вычитание индекса 0 подсписка с индексом 1 предыдущий подсписок. Это самый оптимизированный способ добиться того, чего вы хотите.

Answer 3

Вы можете сделать что-то вроде этого,

In [22]: input_list = [range(1,100),range(102, 200)] 
In [23]: total_list = sum(input_list,[]) 
In [24]: master_total_list = range(min(total_list),max(total_list)+1) 
In [25]: [i for i in master_total_list if i not in total_list] 
Out[25]: [100, 101] 

Answer 4

Try наборы для решения этой проблемы:

test = set(range(1, 100 + 1) + range(102, 200 + 1)) 
missing = list(set(range(min(test), max(test))) - test) 
print (missing)