Effiziente Methode, um fehlende Elemente in einer Ganzzahl zu finden

Question

Angenommen, zwei Elemente fehlen in einer Folge aufeinanderfolgender Ganzzahlen und die fehlenden Elemente liegen zwischen dem ersten und letzten Element. Ich habe einen Code geschrieben, der die Aufgabe erfüllt. Ich wollte es jedoch effizienter machen, wenn es möglich ist, weniger Schleifen zu verwenden. Jede Hilfe wird geschätzt. Auch was ist mit der Bedingung, wenn wir mehr fehlende Elemente (sagen wir nahe bei n/4) statt 2 finden müssen. Ich denke, dann sollte mein Code effizient sein, weil ich früher aus der Schleife ausbricht?

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

dass L Unter der Annahme ist eine Liste von ganzen Zahlen ohne Duplikate, können Sie daraus schließen, dass der Teil der Liste zwischen Start- und Index ist vollständig aufeinander folgend genau dann, wenn L[index] == L[start] + (index - start) und ähnlich mit Index und Ende ist vollständig aufeinander folgend wenn und nur wenn L[index] == L[end] - (end - index). Dies kombiniert mit dem Aufteilen der Liste in zwei rekursiv ergibt eine sublineare Lösung.

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

Answer 2

Wenn die Eingangssequenz ist sortiert, könnten Sie setzt hier verwenden. Nimm die Start- und Endwerte aus der Eingabeliste:

def missing_elements(L): 
    start, end = L[0], L[-1] 
    return sorted(set(range(start, end + 1)).difference(L)) 

Dies setzt Python 3 voraus; Verwenden Sie für Python 2 xrange(), um zu vermeiden, zuerst eine Liste zu erstellen.

Der Aufruf sorted() ist optional; Ohne es wird ein set() der fehlenden Werte zurückgegeben, damit erhalten Sie eine sortierte Liste.

Demo:

>>> L = [10,11,13,14,15,16,17,18,20] 
>>> missing_elements(L) 
[12, 19] 

Ein weiterer Ansatz besteht darin, die durch Lücken zwischen aufeinanderfolgenden Nummern zu erfassen; mit einer älteren itertools library sliding window recipe:

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) 

Dies ist eine reine O (n) -Operation, und wenn Sie die Anzahl der fehlenden Elemente kennen, können Sie es produziert nur diejenigen, stellen Sie sicher, und hält dann an:

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

Dies wird auch größere Lücken bewältigen; wenn Sie fehlen 2 Artikel 11 und 12, es wird immer noch funktionieren:

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

und die obige Probe hatte nur über [10, 13] iterieren um dies herauszufinden.

Answer 3

Hier ist ein Einzeiler:

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] 

Ich benutze die Liste, schneiden die Kopien von einem zu kompensieren, und verwenden Sie aufzuzählen, die Indizes der fehlenden Artikel zu erhalten.

Für lange Listen ist das nicht großartig, weil es nicht O ist (log (n)), aber ich denke, es sollte ziemlich effizient im Vergleich zu einem set für kleine Eingänge sein. izip von itertools würde es wahrscheinlich noch schneller machen.

Answer 4

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

Answer 5

Meine Meinung war keine Schleifen und setzen Operationen zu verwenden:

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

Answer 6

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

Ausgang:

[12, 19] 

Answer 7

einfach die Liste gehen und schauen für nicht fortlaufende Nummern:

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 

Answer 8

Wir fanden einen fehlenden Wert, wenn die Differenz zwischen zwei aufeinanderfolgenden Zahlen größer als 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] 

Hinweis: Python 3. In Python 2 Verwendung itertools.izip.

Verbesserte Version für mehr als ein Wert in einer Zeile fehlt:

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

Answer 9

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

Answer 10

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

Zeit es:

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

7 8 

100000000 loops, best of 3: 0.0181 usec per loop 

Andere Option ist:

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

Und das Timing ist:

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

Answer 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:]) 

Answer 12

Zuerst sollten wir die Liste sortieren und dann prüfen wir für jedes Element, mit Ausnahme der letzten, wenn der nächste Wert in der Liste ist. Seien Sie vorsichtig, keine Duplikate in der Liste zu haben!

l.sort() 

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