Top K Frequent Elements
Du erhältst ein Array aus ganzen Zahlen nums und eine ganze Zahl k. Gib die k Werte zurück, die in nums am häufigsten vorkommen, in absteigender Häufigkeit. Wenn zwei Werte gleich oft vorkommen, kommt der kleinere Wert zuerst.
Jeder Wert kommt in der Antwort nur einmal vor, unabhängig davon, wie oft er in nums vorkommt, und k ist nie größer als die Anzahl der verschiedenen Werte.
Funktion
- numsinteger-array
- die zu zählenden Werte
- kinteger
- Wie viele Werte zurückgegeben werden sollen
- Gibt zurückinteger-array
- die k häufigsten Werte, zuerst die am häufigsten vorkommenden; bei Gleichstand zuerst der kleinere Wert
Einschränkungen
1 ≤ nums.length ≤ 104-104 ≤ nums[i] ≤ 1041 ≤ k, undkist höchstens die Anzahl der verschiedenen Werte innums.
Beispiele
- Eingabe
- nums = [4, 1, 4, 2, 1, 4, 3, 1, 4]k = 2
- Ausgabe
- [4, 1]
- Erklärung
4kommt viermal vor,1dreimal und2und3jeweils einmal. Die beiden häufigsten Werte sind4und danach1.
- Eingabe
- nums = [5, -2, 7, -2, 7, 5, 9]k = 2
- Ausgabe
- [-2, 5]
- Erklärung
-2,5und7kommen jeweils zweimal und9einmal vor. Drei Werte liegen gleichauf an der Spitze, daher sind die beiden kleineren,-2und5, die Antwort.
- Eingabe
- nums = [8]k = 1
- Ausgabe
- [8]
- Erklärung
- Es gibt einen Wert, daher ist er am häufigsten.
+16 versteckte Tests beim Einreichen
Tipps
Öffne sie nacheinander. Jeder verrät ein bisschen mehr.
Finde zunächst heraus, wie oft jeder Wert vorkommt. Welche Datenstruktur ordnet einem Wert in einem Durchlauf seine Häufigkeit zu?
Mit den Zählwerten zur Hand möchtest du die
kbesten Werte nach einer Sortierung bestimmen: Zuerst kommt die höhere Häufigkeit, bei Gleichstand der kleinere Wert. Alle unterschiedlichen Werte zu sortieren funktioniert. Ein Min-Heap der Größekbehält nur die Werte, die noch Teil der Antwort werden können.Eine Häufigkeit ist eine ganze Zahl von 1 bis
n. Erstelle für jede Häufigkeit einen Bucket, wobei Bucketcdie Werte enthält, die genauc-mal vorkommen, und lies die Buckets von der höchsten Häufigkeit abwärts. Fülle die Buckets, indem du die Werte vom kleinsten zum größten durchgehst; so sind die Werte in jedem Bucket bereits in der richtigen Reihenfolge bei Gleichstand.
Lösung
Das Zählen ist der schnelle Teil: Ein Durchlauf mit einer Hash-Map liefert die Anzahl jedes Werts. Die eigentliche Frage ist, wie du die k besten Werte auswählst, ohne mehr Arbeit zu investieren als nötig. Das Sortieren aller d verschiedenen Werte nach ihrer Anzahl kostet O(d log d), ein Min-Heap der Größe k reduziert den Aufwand auf O(d log k), und da eine Anzahl eine ganze Zahl von 1 bis n ist, ordnet ein Bucket-Sort die Werte nach ihrer Anzahl ganz ohne Vergleiche.
Nach Anzahl zählen und dann sortieren
Idee
Zähle zuerst. Ein Durchlauf mit einer Hashmap von Wert zu Anzahl macht aus [4, 1, 4, 2, 1, 4, 3, 1, 4] 4 → 4, 1 → 3, 2 → 1, 3 → 1.
Bringe dann die verschiedenen Werte in die Reihenfolge der Antwort: zuerst die höhere Anzahl und bei gleicher Anzahl zuerst den kleineren Wert. Gib der Sortierung genau diesen Vergleich vor, mit der Anzahl als erstem Schlüssel und dem Wert als zweitem; die ersten k Einträge der sortierten Liste sind die Antwort. Hier lautet die Reihenfolge 4, 1, 2, 3, und k = 2 behält 4 und 1.
Das Zählen kostet O(n). Das Sortieren der d verschiedenen Werte kostet O(d log d), höchstens O(n log n), wenn sich alle Werte unterscheiden: 10^4 Werte erfordern etwa 1.3 × 10^5 Vergleiche, was schnell ist. Der Nachteil ist, dass die Sortierung jeden Wert ordnet, obwohl nur die ersten k wichtig sind.
Algorithmus
- Zähle jeden Wert in einer Hash-Map.
- Füge die unterschiedlichen Werte einer Liste hinzu.
- Sortiere die Liste nach der Häufigkeit absteigend und bei gleicher Häufigkeit nach dem Wert aufsteigend.
- Gib die ersten
kWerte zurück.
from collections import Counter
def topKFrequent(nums, k):
counts = Counter(nums)
# Most frequent first; equal counts put the smaller value first.
ordered = sorted(counts, key=lambda value: (-counts[value], value))
return ordered[:k]Behalte die k besten Elemente in einem Min-Heap
Idee
Du benötigst nur die k besten Werte und hältst daher nur k Kandidaten vor. Bei jedem neuen Wert stellt sich die Frage, ob er den schwächsten Kandidaten schlägt, den du vorhältst. Schwächer bedeutet dabei eine niedrigere Anzahl oder dieselbe Anzahl und einen größeren Wert. Ein Min-Heap, der nach dieser Regel geordnet ist, hält den schwächsten Kandidaten an der Spitze. Dort kannst du ihn in O(1) auslesen und in O(log k) ersetzen.
Gehe die unterschiedlichen Werte durch. Solange der Heap weniger als k Werte enthält, füge den Wert hinzu. Danach ersetzt ein Wert, der den obersten schlägt, diesen; ein Wert, der das nicht tut, wird verworfen, da bereits k bessere Werte vorgehalten werden. Mit einem Heap aus einer Bibliothek ist es kürzer, jeden Wert einzufügen und einmal zu entnehmen, sobald der Heap größer als k wird. So bleiben dieselben k Werte erhalten.
Am Ende enthält der Heap die Antwort, aber nicht in der richtigen Reihenfolge: Ein Heap ist nur teilweise sortiert. Beim Entnehmen erhältst du zuerst den schwächsten Wert. Schreibe die Antwort daher von der letzten Position rückwärts bis zur ersten.
Jeder der d unterschiedlichen Werte erfordert höchstens eine Heap-Operation auf k Einträgen, daher dauert die Auswahl O(d log k). Das ist schneller als Sortieren, wenn k viel kleiner als d ist, zum Beispiel bei den obersten 10 von 8000 unterschiedlichen Werten.
Algorithmus
- Zähle jeden Wert in einer Hash-Map.
- Füge jeden unterschiedlichen Wert hinzu, solange der Heap weniger als
kWerte enthält. - Vergleiche, sobald der Heap voll ist, den Wert mit dem obersten Element, dem schwächsten beibehaltenen Wert. Ist der neue Wert stärker, setze ihn an die Spitze und lasse ihn nach unten durchsickern.
- Entferne
k-mal das oberste Element des Heaps und schreibe jeden Wert in die Antwort, beginnend bei der letzten Position bis zur ersten.
import heapq
from collections import Counter
def topKFrequent(nums, k):
counts = Counter(nums)
# Entries are (count, -value). heapq keeps the smallest entry on top, which is
# the weakest value kept: the lowest count, and on a tie the larger value.
heap = []
for value, count in counts.items():
heapq.heappush(heap, (count, -value))
if len(heap) > k:
heapq.heappop(heap)
# Pops come out weakest first, so fill the answer from the back.
result = [0] * k
for i in range(k - 1, -1, -1):
result[i] = -heapq.heappop(heap)[1]
return resultNach Häufigkeit zählen und anschließend per Bucket Sort sortieren
Idee
c die Werte enthält, die genau c-mal vorkommen, und lies die Buckets von Bucket n abwärts aus. Die Werte kommen in der Reihenfolge absteigender Häufigkeit heraus, und es werden niemals zwei Häufigkeiten miteinander verglichen.Die Regel für Gleichstände verlangt noch etwas: Innerhalb eines Buckets muss der kleinere Wert zuerst kommen. Die Werte liegen zwischen -10^4 und 10^4, daher kann ein Array aus R = 2 × 10^4 + 1 Zählern die Häufigkeiten zählen; der Wert v steht am Index v + 10^4. Gehe dieses Array vom kleinsten bis zum größten Wert durch und füge jeden Wert dem Bucket seiner Häufigkeit hinzu. Jeder Bucket füllt sich in aufsteigender Reihenfolge, also in der Reihenfolge für Gleichstände, sodass nichts sortiert werden muss.
Für [5, -2, 7, -2, 7, 5, 9] fügt der Durchlauf -2, 5, 7 in dieser Reihenfolge in Bucket 2 ein und 9 in Bucket 1. Wenn du ab Bucket 7 abwärts liest, ist der erste Bucket mit Werten Bucket 2, und k = 2 nimmt -2 und 5.
Der Aufwand besteht aus einem Durchlauf über nums, einem Durchlauf über die R Zähler und einem Durchlauf über die Buckets, insgesamt also O(n + R): linear bei einem festen Wertebereich. Mit einer Hash-Map anstelle des Zählarrays bleibt das Zählen linear, aber die Buckets füllen sich in der Reihenfolge der Map, und du müsstest jeden Bucket sortieren, um die Regel für Gleichstände einzuhalten.
Algorithmus
- Zähle jeden Wert in einem Array mit dem Index
value + 10^4. - Erstelle Buckets von 1 bis
n, eine Liste pro möglicher Anzahl. - Gehe das Zählarray vom kleinsten zum größten Wert durch und füge jeden vorkommenden Wert dem Bucket seiner Anzahl hinzu.
- Lies die Buckets von der Anzahl
nabsteigend bis 1 und entnimm Werte, bis dukhast.
def topKFrequent(nums, k):
OFFSET = 10000 # values run from -10^4 to 10^4
counts = [0] * (2 * OFFSET + 1)
for x in nums:
counts[x + OFFSET] += 1
# buckets[c] lists the values that occur exactly c times. Walking the
# values from smallest to largest fills every bucket in ascending order.
buckets = [[] for _ in range(len(nums) + 1)]
for i, c in enumerate(counts):
if c > 0:
buckets[c].append(i - OFFSET)
# Read the buckets from the highest count down until k values are taken.
result = []
for c in range(len(nums), 0, -1):
for value in buckets[c]:
result.append(value)
if len(result) == k:
return result
return result
Stolperfallen und Grenzfälle
Die Zählung ist selten falsch. Die Reihenfolge der Antwort ist es.
- Gleichstände nach dem ersten Auftreten oder der Reihenfolge in der Hash-Map auflösen. Im zweiten Beispiel kommen
-2,5und7alle zweimal vor, und nur die Regel „kleinerer Wert“ macht[-2, 5]zur einzig richtigen Antwort. - Das Array des Heaps so zurückgeben, wie es ist. Ein Heap ist nur teilweise geordnet, und sein oberster Wert ist der schwächste – derjenige, der zuletzt hingehört.
- Die Gleichstandsregel des Heaps falsch herum anwenden. Von zwei Werten mit derselben Häufigkeit ist der größere der schwächere, daher entfernt ein Min-Heap auf
(count, value)den falschen Wert. Verwende(count, -value)oder einen für die Regel geschriebenen Vergleich. - Nur so viele Buckets anlegen, wie es unterschiedliche Werte gibt. Ein Wert kann
nMal vorkommen, wie in[3, 3, 3, 3], daher muss Bucketnexistieren. - In Java zwei
Integer-Häufigkeiten mit!=vergleichen. Dabei werden Referenzen verglichen, und das führt zu Fehlern, sobald die Häufigkeiten 127 überschreiten. Entpacke sie zuerst zuint. - Am Ende einen ganzen Bucket übernehmen. Höre auf, sobald du
kWerte hast, auch mitten in einem Bucket.
Häufige Fragen4
Wie hoch ist die Zeitkomplexität von „Top K Frequent Elements“?
Das Zählen benötigt O(n). Die Auswahl der häufigsten k Elemente kostet dann O(d log d) beim Sortieren der d verschiedenen Werte, O(d log k) mit einem Min-Heap der Größe k und O(n) plus einen Durchlauf über den Wertebereich beim Bucket-Sort. Da d bis n reichen kann, liegt die Sortierung im schlimmsten Fall bei O(n log n), während Bucket-Sort linear ist.
Kann man die Top K Frequent Elements in O(n)-Zeit lösen?
Ja, mit Bucket Sort. Die Anzahlen sind ganze Zahlen von 1 bis n, daher kommt jeder Wert in den Bucket seiner Anzahl. Liest man die Buckets von der höchsten Anzahl abwärts aus, erhält man die Werte nach Häufigkeit sortiert, ohne einen vergleichsbasierten Sortieralgorithmus zu verwenden. Quickselect auf den Anzahlen hat im Durchschnitt ebenfalls eine Laufzeit von O(n), im Worst Case ist die Laufzeit jedoch quadratisch.
Warum einen Min-Heap und keinen Max-Heap verwenden?
Ein Max-Heap mit allen d-Werten funktioniert ebenfalls: Er wird in O(d) aufgebaut und k-mal entfernt, insgesamt also O(d + k log d). Ein Min-Heap der Größe k enthält nur k Einträge und eignet sich für Werte, die einzeln eintreffen, da sein oberstes Element der Kandidat zum Entfernen ist. Der Nachteil ist, dass er das Ergebnis in umgekehrter Reihenfolge liefert, also füllst du das Ergebnis von hinten.
Wie löst man Gleichstände bei den Top K häufigsten Elementen auf?
Wähle eine Regel und wende sie überall an; hier stehen bei gleicher Häufigkeit die kleineren Werte zuerst, wodurch die Antwort eindeutig ist. Bei einer Sortierung werden zuerst die Häufigkeiten und dann die Werte verglichen. Bei einem Heap ist von zwei Werten mit gleicher Häufigkeit der größere Wert der schwächere. Fülle beim Bucket-Sort die Buckets in aufsteigender Reihenfolge der Werte, dann ist jeder Bucket bereits in der Reihenfolge für Gleichstände sortiert.
Ähnliche Aufgaben
Aufgaben mit denselben Ideen. Wer zwei oder drei davon löst, behält das Muster.
Python
def topKFrequent(nums, k):
# Schreibe hier den CodeFall 1
Fall 2
Fall 3
Eingabe
nums = [4, 1, 4, 2, 1, 4, 3, 1, 4] k = 2
Erwartet
[4, 1]