Listeneinträge in der Reihenfolge ihrer Häufigkeit drucken

Question

Nehmen wir an, wir haben ein Array von Ganzzahlen oder sogar kontinuierlichen Ganzzahlen. Die Idee besteht darin, einzigartige Elemente in absteigender Reihenfolge basierend auf Häufigkeit des Auftretens zu drucken. Zum Beispiel, für 7, 4, 2, 4, 9, 6, 5, 6, 2, 0, 2, 1 sollten wir: 2, 4, 6, 7, 9, 5, 0, 1 als 2 erscheint drei mal, 4 und 6 zweimal und der Rest nur einmal.

Gibt es einen besseren und effizienteren Ansatz als (sorting map based by value) das Vorkommen von Elementen zu zählen, sie in der Karte zu speichern und dann die Karte basierend auf Wert zu sortieren.

Answer 1

Es scheint mir jedoch, dass es einen sehr effektiven Algorithmus dafür geben sollte, da es wahrscheinlich eine Möglichkeit gibt, Frequenzen beim Fliegen zu sortieren.

Dieses Problem ist eigentlich Omega(nlogn) im algebraischen Baummodell (Hashing nicht unter diesem Modell erlaubt ist), mit einer Reduktion von Element Distinctness Problem, also wenn Sie haben gehofft, eine eins zu bekommen (oder konstante Zahl) von Iterationen löse es, ohne irgendeine zusätzliche Datenstruktur unter der Haube, um es zu lösen - das ist unmöglich, da es uns erlauben wird, die Elementunterscheidbarkeit in O (n) im algebraischen Baummodell zu lösen.

Die kanonischen Lösungen für diese Art von Problemen sind:

1. (Ihr Vorschlag): Karte Bauen, Duplikate entfernen und sortiert nach Frequenz
2. ähnlich wie 1, aber statt einer Karte - sortieren die Elemente und die Anzahl der Male, die jedes Element wiederholt wird, ist einfach mit der binären Suche.

Answer 2

Wenn Sie Python verwenden dann die collections.Counter-Klasse verwenden und seine Counter.most_common() Methode

from collections import Counter 
counted = Counter([7, 4, 2, 4, 9, 6, 5, 6, 2, 0, 2, 1]) 
ordered = [value for value, count in counted.most_common()] 
print(ordered) # [2, 4, 6, 0, 1, 5, 7, 9] 

Die source eine heapq verfügbar ist zeigt in most_common verwendet wird()

Answer 3

Konzentration auf die Anforderung in der Frage der Annahme der Eingabe als ein Strom von ganzen Zahlen wäre eine Lösung eine modifizierte Einfügesortierung ...

Erstellen Sie eine Liste (sie ein Name countlist) von Listen, zunächst leer. Jedes Mal, wenn Sie einen neuen Wert akzeptieren, durchlaufen Sie die einzelnen Listen in countlist und suchen nach dem Wert. Wenn Sie den Wert in countlist[i] finden, entfernen Sie den Wert aus der aktuellen Liste und fügen Sie ihn in countlist[i+1] ein. Fügen Sie ggf. eine neue Liste zu countlist hinzu. Wenn Sie den Wert nie finden, fügen Sie den Wert in countlist[1] ein.

Der Zweck der Iteration absteigend statt aufsteigend ist, dass Sie einen Zeiger auf, wo der Wert in countlist[i] eingefügt wird, wenn Sie es in countlist[i-1] finden können. Wenn Sie für die Werte, die die gleiche Anzahl haben, keine Untersortierung benötigen, können Sie diesen Zeiger überspringen und aufsteigend iterieren.

Ich glaube, dass dieser Algorithmus insgesamt O (n) ist. Das Verarbeiten jedes neuen Werts ist O (n) und Ergebnisse werden sortiert, wie Sie gehen. Zu jedem Zeitpunkt können Sie die richtige Reihenfolge (bis jetzt) ​​drucken, indem Sie durch countlist iterieren und jede Liste drucken.

Beispiellauf mit dem Beispiel in der Frage ...

input: 7, 4, 2, 4, 9, 6, 5, 6, 2, 0, 2, 1 

After accepting 7: 
countlist[1] = 7 

After accepting 4: 
countlist[1] = 4, 7 

After accepting 2: 
countlist[1] = 2, 4, 7 

After accepting 4: 
countlist[1] = 2, 7 
countlist[2] = 4 

After accepting 9: 
countlist[1] = 2, 7, 9 
countlist[2] = 4 

After accepting 6: 
countlist[1] = 2, 6, 7, 9 
countlist[2] = 4 

After accepting 5: 
countlist[1] = 2, 5, 6, 7, 9 
countlist[2] = 4 

After accepting 6: 
countlist[1] = 2, 5, 7, 9 
countlist[2] = 4, 6 

After accepting 2: 
countlist[1] = 5, 7, 9 
countlist[2] = 2, 4, 6 

After accepting 0: 
countlist[1] = 0, 5, 7, 9 
countlist[2] = 2, 4, 6 

After accepting 2: 
countlist[1] = 0, 5, 7, 9 
countlist[2] = 4, 6 
countlist[3] = 2 

After accepting 1: 
countlist[1] = 0, 1, 5, 7, 9 
countlist[2] = 4, 6 
countlist[3] = 2