Kth Largest Element in a Stream

Q: Warum einen Min-Heap und keinen Max-Heap für das k-größte Element verwenden?

Der kleinste der k größten Werte ist sowohl die Antwort als auch der Wert, den ein Neuzugang übertreffen muss, und ein Min-Heap der Größe k hält ihn ganz oben. Ein Max-Heap mit allen Werten hält den größten ganz oben. Um den k -größten zu erreichen, müssen daher bei jedem neuen Wert k-1 Werte entfernt und wieder eingefügt werden.

Q: Wie hoch ist die Zeitkomplexität des k-größten Elements in einem Datenstrom?

Jede Aufnahme kostet O(log k) : einen Vergleich mit dem obersten Element und höchstens ein Durchsickern durch einen Heap mit k Werten. Der Aufbau des Heaps aus nums kostet O(n log k) , daher benötigt der gesamte Durchlauf O((n + m) log k) Zeit und O(k) zusätzlichen Speicherplatz.

LeichtHeap

+10

Ein Strom von Ganzzahlen beginnt mit den Werten in nums. Dann treffen die Werte von adds nacheinander ein. Erfasse nach jedem Eintreffen den k-größten Wert unter allen bisher gesehenen Werten, wobei gleiche Werte einzeln gezählt werden. Gib die erfassten Werte der Reihe nach zurück, einen für jeden Wert von adds.

nums enthält mindestens k-1 Werte, sodass nach dem ersten Eintreffen immer mindestens k Werte zur Auswahl stehen.

Funktion

kthLargestStream(k: integer, nums: integer-array, adds: integer-array) → integer-array

kinteger: der Rang, der ausgegeben werden soll, 1 für den größten Wert
numsinteger-array: die Werte, die sich bereits im Stream befinden
addsinteger-array: die Werte, die der Reihe nach eintreffen
Gibt zurückinteger-array: der k-größte Wert nach jeder Ankunft

Einschränkungen

1 ≤ nums.length ≤ 10⁴
1 ≤ adds.length ≤ 10⁴
1 ≤ k ≤ nums.length + 1
-10⁴ ≤ nums[i], adds[i] ≤ 10⁴
nums kann in beliebiger Reihenfolge angeordnet sein, und gleiche Werte zählen als eigene Werte.

Beispiele

Eingabe: k = 3nums = [7, 1, 5]adds = [3, 9, 6, 2, 8]
Ausgabe: [3, 5, 6, 6, 7]
Erklärung: Nach 3 kommt die drittgrößte Zahl von 7, 5, 3 und 1: 3. Dann erhöht 9 sie auf 5, 6 erhöht sie auf 6, 2 ändert nichts, und 8 erhöht sie auf 7 (9, 8, 7).

Eingabe: k = 1nums = [-2]adds = [-5, 0, -1, 4]
Ausgabe: [-2, 0, 0, 4]
Erklärung: Bei k = 1 ist die Antwort der bisher größte Wert: -2, bis 0 kommt, nach -1 immer noch 0, dann 4.

Weiterführende Frage

Wie würdest du dieselbe Frage beantworten, wenn Werte auch aus dem Datenstrom entfernt werden könnten?

Tipps

Öffne sie nacheinander. Jeder verrät ein bisschen mehr.

0 von 3 geöffnet

Lösung

Werte verlassen den Datenstrom nie, daher ist ein Wert, der unter den aktuellen k-größten liegt, endgültig ausgeschieden. Behalte nur die k größten Werte in einem Min-Heap: Dessen oberstes Element ist die Antwort, und jedes neu eintreffende Element erfordert einen Vergleich und höchstens eine O(log k)-Heap-Aktualisierung.

Nach jeder Ankunft sortieren

Korrekt, wird aber bei den größten Tests nicht fertig

Idee

Behalte jeden Wert in einer Liste. Sortiere sie nach jedem neu eintreffenden Wert aufsteigend und lies den Index length-k aus, der definitionsgemäß den k-größten Wert enthält.

Bei jedem neu eintreffenden Wert werden bis zu n + m Werte sortiert, wobei n und m die Längen von nums und adds sind. Bei jeweils 10^4 Werten entspricht das insgesamt etwa 2 × 10^9 Vergleichen.

Algorithmus

Kopiere nums in eine Liste values.
Füge für jeden Wert von adds diesen zu values hinzu.
Sortiere values in aufsteigender Reihenfolge und notiere values[length-k].
Gib die notierten Werte zurück.

def kthLargestStream(k, nums, adds):
    values = list(nums)
    result = []
    for x in adds:
        values.append(x)
        values.sort()
        # In increasing order the k-th largest sits k places from the end.
        result.append(values[len(values) - k])
    return result

Min-Heap der k größten Werte

Idee

Sobald ein Wert k größere Werte über sich hat, bleibt das für den Rest des Datenstroms so. Daher sind nur die bisher gesehenen k größten Werte relevant. Speichere sie in einem Min-Heap. Sein oberstes Element ist das kleinste der k größten Werte und damit genau der insgesamt k-größte Wert.

Wenn x eintrifft und der Heap voll ist, vergleiche es mit dem obersten Element. Ist x nicht größer, gehört es nicht zu den k größten Werten und es ändert sich nichts. Ist es größer, fällt das oberste Element heraus: Ersetze es durch x und führe ein Sift-down aus, in O(log k). Die Startwerte durchlaufen dieselbe Routine, daher kann nums länger als k sein.

Im ersten Beispiel enthält der Heap nach nums die Werte 7, 1 und 5, wobei 1 oben liegt. Der eintreffende Wert 3 ersetzt 1, und das oberste Element, 3, ist die erste Antwort.

Algorithmus

Beginne mit einem leeren Min-Heap.
Um x hinzuzufügen: Wenn der Heap weniger als k Werte enthält, füge x hinzu. Andernfalls, wenn x größer als das oberste Element ist, ersetze das oberste Element durch x und stelle die Heap-Ordnung wieder her.
Füge auf diese Weise jeden Wert aus nums hinzu.
Füge jeden Wert aus adds hinzu und notiere das oberste Element des Heaps.
Gib die notierten Werte zurück.

import heapq


def kthLargestStream(k, nums, adds):
    # A min-heap of the k largest values so far; heap[0] is the smallest of them.
    heap = []

    def add(x):
        if len(heap) < k:
            heapq.heappush(heap, x)
        elif x > heap[0]:
            heapq.heapreplace(heap, x)  # drop the top, add x

    for x in nums:
        add(x)
    result = []
    for x in adds:
        add(x)
        result.append(heap[0])  # the k-th largest so far
    return result

Stolperfallen und Grenzfälle

Doppelte Werte entfernen. Die vier größten Werte unter 9, 6, 6, 6, 2 sind 9, 6, 6 und 6. Eine Menge oder eine Prüfung, die bereits vorhandene Werte überspringt, gibt im dritten Beispiel 2 statt 6 zurück.
Die Antwort vor dem Hinzufügen ablesen. Wenn nums k-1 Werte enthält, ist der Heap erst nach dem ersten Hinzufügen voll. Füge also zuerst den Wert hinzu und lies dann das oberste Element aus.
Nach dem Sortieren vom falschen Ende zählen. In aufsteigender Reihenfolge befindet sich das k-größte Element am Index length-k; am Index k-1 befindet sich das k-kleinste Element.
Die Standardreihenfolge des Heaps verwenden. C++s priority_queue und Rusts BinaryHeap sind Max-Heaps: Übergib greater<int> oder verpacke die Werte in Reverse.

Häufige Fragen3

Warum einen Min-Heap und keinen Max-Heap für das k-größte Element verwenden?

Der kleinste der k größten Werte ist sowohl die Antwort als auch der Wert, den ein Neuzugang übertreffen muss, und ein Min-Heap der Größe k hält ihn ganz oben. Ein Max-Heap mit allen Werten hält den größten ganz oben. Um den k-größten zu erreichen, müssen daher bei jedem neuen Wert k-1 Werte entfernt und wieder eingefügt werden.

Wie hoch ist die Zeitkomplexität des k-größten Elements in einem Datenstrom?

Jede Aufnahme kostet O(log k): einen Vergleich mit dem obersten Element und höchstens ein Durchsickern durch einen Heap mit k Werten. Der Aufbau des Heaps aus nums kostet O(n log k), daher benötigt der gesamte Durchlauf O((n + m) log k) Zeit und O(k) zusätzlichen Speicherplatz.

Kann das k-größte Element in einem Stream mit einer sortierten Liste bestimmt werden?

Ja. Halte alle Werte sortiert, füge jeden neu eintreffenden Wert mithilfe der binären Suche an der richtigen Stelle ein und lies den Wert an der Position k vom Ende aus. Die Suche benötigt O(log n), aber das Verschieben der Werte nach der Einfügestelle benötigt pro Ankunft O(n): etwa 1.5 × 10^8 Verschiebungen bei 10^4 Startwerten und 10^4 Ankünften.

def kthLargestStream(k, nums, adds):
    # Schreibe hier den Code

Test #1

Test #2

Test #3

Argumente

k = 3
nums = [7, 1, 5]
adds = [3, 9, 6, 2, 8]

Erwartete Ausgabe

[3, 5, 6, 6, 7]