Optimieren der Min-Funktion zum Ändern von Listen

Question

Ich habe es mit einem Problem zu tun, bei dem ich die Mindestanzahl in einer Liste verfolgen muss. Diese Liste nimmt jedoch ständig ab, sagen wir von einer Million Elemente zu einem einzelnen Element. Ich suchte nach einer Möglichkeit, den Mindestwert nicht jedes Mal zu überprüfen, wenn ich eine kleinere Liste mit einem Element erhielt. Wie das Mindestelement zu verfolgen und wenn es entfernt wird, wird das nächste Minimum das Minimum. Ich möchte dies in linearer Zeit erreichen (es sollte erreichbar sein angesichts der Mechanik des Problems)

Woran ich gedacht habe, seit ich damit angefangen habe, kann ich collections Counter verwenden, um Elemente in der Liste zu zählen. Dann finde ich das Minimum (schon O(2*n)), und jedes Mal, wenn ich ein Element entferne, subtrahiere ich 1 vom Wert des Wörterbuchschlüssels. Wenn jedoch die Anzahl der minimalen Anzahl erschöpft ist, würde ich immer noch das zweite minimale Element finden müssen, um es zu ersetzen.

Bitte helfen Sie mir eine Lösung zu finden. Ich würde sagen, das ist ein interessantes Problem.

Answer 1

Angenommen, Ihr Programm einig Zeit es zu sortieren dauern würde, jedes Mal, wenn die Liste

a = [10,9,10,8,7,6,5,4,3,2,1,1,1,0] # you're just removing 
a = sorted(a) #sort ascending 

# then you remove stuff from your list 
# but always a[0] is minimum element 

min = a[0] #you must be careful, there must be at least one item so check that before 
#getting the min 

gibt also keine Notwendigkeit für die Suche