Kth Largest Element in an Array
Du erhältst ein Array aus ganzen Zahlen nums und eine ganze Zahl k. Gib den k-größten Wert in nums zurück: den Wert an Position k, von 1 an gezählt, nachdem das Array von größtem nach kleinstem Wert sortiert wurde.
Gleiche Werte werden separat gezählt. In [5, 5, 1] ist der größte Wert 5 und der zweitgrößte ebenfalls 5.
Funktion
- numsinteger-array
- die zu ordnenden Werte
- kinteger
- welcher größte Wert zurückgegeben werden soll, 1 für den größten
- Gibt zurückinteger
- der k-größte Wert, wobei Duplikate mitgezählt werden
Einschränkungen
1 ≤ k ≤ nums.length ≤ 104-104 ≤ nums[i] ≤ 104- Gleiche Werte zählen als separate Werte.
Beispiele
- Eingabe
- nums = [7, 2, 9, 4, 9, 1]k = 2
- Ausgabe
- 9
- Erklärung
- Von den größten bis zu den kleinsten Werten sind es
9, 9, 7, 4, 2, 1. Die beiden 9er werden einzeln gezählt, daher ist der zweitgrößte Wert9und nicht7.
- Eingabe
- nums = [5, -3, 8, 0, 2]k = 4
- Ausgabe
- 0
- Erklärung
- Von der größten zur kleinsten Zahl lauten die Werte
8, 5, 2, 0, -3, und der vierte davon ist0.
- Eingabe
- nums = [6]k = 1
- Ausgabe
- 6
- Erklärung
- Bei nur einem Wert und
k = 1ist dieser Wert der größte.
+15 versteckte Tests beim Einreichen
Weiterführende Frage
Die Werte treffen jetzt nacheinander ein. Kannst du nach jedem Eintreffen den Median aller bisher gesehenen Werte in O(log n) Zeit pro Wert angeben?
Tipps
Öffne sie nacheinander. Jeder verrät ein bisschen mehr.
Absteigend sortiert befindet sich die Antwort an einer bekannten Position. An welcher? Und brauchst du alle anderen Werte, um sie zu kennen?
Der k-größte Wert ist der kleinste der
kgrößten Werte. Wenn du nur diekgrößten bisher gesehenen Werte behältst, mit welchem davon vergleichst du einen neuen Wert?Behalte einen Min-Heap mit höchstens
kWerten. Ein neuer Wert ersetzt das oberste Element, wenn er größer ist; das oberste Element ist am Ende die Antwort. Für eine durchschnittliche Laufzeit vonO(n)partitioniere wie bei Quicksort um ein zufälliges Pivot und behalte nur die Seite, die den Indexn-kenthält.
Lösung
Sortieren und das Ablesen einer Position beantworten die Frage, und hier ist das schnell genug. Ein Interviewer möchte sehen, wie viel von dieser Sortierung du überspringen kannst, denn du brauchst eine Position, nicht alle n. Ein Min-Heap der Größe k behält nur die Werte, die noch die Antwort sein können, und Quickselect partitioniert wie Quicksort, verfolgt aber nur die Seite, auf der sich die Antwort befindet. Dadurch sinkt die durchschnittliche Laufzeit auf O(n).
Eine Position sortieren und lesen
Idee
Der k-größte Wert wird durch die sortierte Reihenfolge definiert, also bringe die Werte in diese Reihenfolge. Absteigend sortiert wird aus [7, 2, 9, 4, 9, 1] die Folge [9, 9, 7, 4, 2, 1], und der k-größte Wert steht an Index k-1. Für k = 2 ist das Index 1, die zweite 9. Wenn deine Sortierung den kleinsten Wert zuerst setzt, lies stattdessen den Index n-k aus: Index 4 von [1, 2, 4, 7, 9, 9] ist derselbe 9.
Duplikate erfordern keine besondere Behandlung: Beim Sortieren bleibt jede Kopie erhalten, und jede Kopie nimmt ihre eigene Position ein.
Bei n = 10^4 führt eine Sortierung etwa n log n ≈ 1.3 × 10^5 Vergleiche durch, womit alle Tests bestanden werden. Der Nachteil ist, dass alle n Werte sortiert werden, obwohl nur eine Position wichtig ist. Die nächsten beiden Ansätze leisten weniger dieser Arbeit.
Algorithmus
- Kopiere
nums, damit das Array des Aufrufers unverändert bleibt. - Sortiere die Kopie. Verwende einen numerischen Vergleich; manche Sprachen vergleichen Zahlen standardmäßig als Text.
- Gib den Index
k-1einer absteigend sortierten Reihenfolge zurück oder den Indexn-keiner aufsteigend sortierten Reihenfolge.
def findKthLargest(nums, k):
# Largest first: the k-th largest sits at index k-1.
ordered = sorted(nums, reverse=True)
return ordered[k - 1]Die k größten Elemente in einem Min-Heap behalten
Idee
Der k-größte Wert ist der kleinste der k größten Werte. Durchlaufe also nums einmal und behalte in einem Min-Heap nur die k größten bisher gesehenen Werte. Die Spitze eines Min-Heaps ist sein kleinster Wert und damit genau der mögliche Antwortwert.
Wenn ein Wert x eintrifft und der Heap weniger als k Werte enthält, füge ihn hinzu. Andernfalls vergleiche x mit der Spitze. Ist x nicht größer, sind mindestens k der gespeicherten Werte mindestens so groß wie x, also kann x niemals die Antwort sein und du überspringst ihn. Ist x größer, ist die Spitze aus den k größten Werten herausgefallen: Ersetze sie durch x. In Beispiel 2 mit k = 4 füllen die ersten vier Werte den Heap mit 5, -3, 8, 0, und die Spitze ist -3. Dann ist 2 größer als -3 und ersetzt ihn; die Spitze wird zu 0, und 0 ist die Antwort.
Jeder Wert erfordert höchstens eine Heap-Operation mit Kosten von O(log k), also beträgt der Gesamtaufwand O(n log k) Zeit und O(k) Speicher. Das ist bei kleinem k schneller als Sortieren und funktioniert auch mit einem Datenstrom: Du musst nie alle Werte gleichzeitig speichern. Python bietet heapq, Java PriorityQueue, C++ priority_queue mit greater, Go container/heap, Rust BinaryHeap mit Reverse und PHP SplMinHeap. Der Code für die anderen Sprachen implementiert den Heap in einem Array, in dem die Kinder des Index i an den Positionen 2i+1 und 2i+2 liegen – oder in Lua und R, die ab 1 zählen, an den Positionen 2i und 2i+1.
Algorithmus
- Beginne mit einem leeren Min-Heap.
- Füge jeden Wert
xhinzu, solange der Heap weniger alskWerte enthält. - Sobald er
kWerte enthält, ersetze das oberste Element nur dann durchx, wennxgrößer als das oberste Element ist. - Gib nach dem letzten Wert das oberste Element des Heaps zurück.
import heapq
def findKthLargest(nums, k):
# A min-heap of the k largest values so far; its top is the smallest of them.
heap = []
for x in nums:
if len(heap) < k:
heapq.heappush(heap, x)
elif x > heap[0]:
heapq.heapreplace(heap, x) # drop the top, add x
return heap[0]Quickselect mit einer Dreiwegepartition
Idee
Quicksort wählt ein Pivot-Element und partitioniert: kleinere Werte links davon, größere Werte rechts davon. Nach einer Partition befindet sich das Pivot-Element an seinem endgültigen sortierten Index, auch wenn keine der beiden Seiten bereits sortiert ist. Quickselect nutzt diese Tatsache. Bei aufsteigender Sortierung liegt die Antwort am Index target = n-k. Nach einer Partition liegt target entweder links vom Pivot-Element, an dessen Position oder rechts davon. Daher machst du auf einer Seite weiter und verwirfst die andere.
Für [7, 2, 9, 4, 9, 1] und k = 2 ist target gleich 6-2 = 4. Partitioniere um 4: 2 und 1 erhalten die Indizes 0 und 1, 4 erhält Index 2 und 7, 9, 9 erhalten die Indizes 3 bis 5. Index 4 liegt rechts, also behältst du nur die Indizes 3 bis 5. Partitioniere diese um 9: 7 erhält Index 3 und beide 9er erhalten die Indizes 4 und 5. An Index 4 steht eine 9, also lautet die Antwort 9.
Verwende eine Dreifach-Partitionierung: Werte kleiner als das Pivot-Element, dann Werte gleich dem Pivot-Element, dann Werte größer als das Pivot-Element, nachverfolgt durch lt und gt. Der Gleichheitsblock [lt, gt] befindet sich an seiner sortierten Position. Fällt target in diesen Block, bist du fertig. Bei einer einfachen Zweifach-Partitionierung wird ein Array aus 10^4 Kopien von 7 pro Runde um einen Wert kleiner, also sind etwa 5 × 10^7 Schritte nötig; die Dreifach-Variante löst das in einem Durchlauf.
Wähle das Pivot-Element zufällig. In der Hälfte der Fälle liegt es in der mittleren Hälfte des Bereichs, wodurch der Bereich auf höchstens drei Viertel schrumpft. Die erwartete Arbeit entspricht daher einigen Durchläufen über n Werte: O(n). Im Worst Case bleibt es bei O(n²), wenn jedes Pivot-Element ein Extremwert ist; eine feste Wahl wie das erste Element führt bei sortierter Eingabe zu diesem Fall. Der Code arbeitet mit einer Kopie, was O(n) Speicher benötigt. Wenn du die Eingabe ändern darfst, lässt sich dieser Aufwand durch Partitionieren von nums selbst auf O(1) senken.
Algorithmus
- Kopiere
numsnacha, setzetarget = n-k,lo = 0undhi = n-1. - Wähle einen zufälligen Pivot aus
a[lo..hi]. - Partitioniere
a[lo..hi]in Werte unter, gleich und über dem Pivot, sodass die gleichen Werte ina[lt..gt]verbleiben. - Falls
target < lt, setzehi = lt-1; fallstarget > gt, setzelo = gt+1; andernfalls gib den Pivot zurück. - Wiederhole den Vorgang ab Schritt 2.
import random
def findKthLargest(nums, k):
a = list(nums)
target = len(a) - k # the answer's index once a is sorted smallest first
lo, hi = 0, len(a) - 1
while True:
pivot = a[random.randint(lo, hi)]
# Three-way partition of a[lo..hi]: < pivot, then == pivot, then > pivot.
lt, i, gt = lo, lo, hi
while i <= gt:
if a[i] < pivot:
a[lt], a[i] = a[i], a[lt]
lt += 1
i += 1
elif a[i] > pivot:
a[i], a[gt] = a[gt], a[i]
gt -= 1
else:
i += 1
# Now a[lt..gt] all equal pivot, and they are in their sorted places.
if target < lt:
hi = lt - 1
elif target > gt:
lo = gt + 1
else:
return pivot
Stolperfallen und Grenzfälle
Die meisten falschen Antworten entstehen durch Duplikate und dadurch, dass die beiden Arten, Positionen zu zählen, verwechselt werden.
- Zuerst Duplikate entfernen. Das Problem zählt jede Kopie: Bei
[7, 2, 9, 4, 9, 1]mitk = 2lautet die Antwort9, aber nachdem das Array in eine Menge umgewandelt wurde, ist sie7. - Den falschen Index verwenden.
kwird ab 1 gezählt, daher steht die Antwort beim Sortieren in absteigender Reihenfolge am Indexk-1und beim Sortieren in aufsteigender Reihenfolge am Indexn-k, nichtn-k-1. - Zahlen als Text sortieren. In JavaScript und TypeScript ergibt
[10, 9, 2].sort()den Wert[10, 2, 9]. Übergib(a, b) => a - b. - Einen Max-Heap der Größe
kverwenden. Das Entfernen des größten Werts behält diekkleinsten Werte und gibt den k-kleinsten Wert zurück. - Quickselect mit einer Zwei-Wege-Partitionierung oder einem festen Pivot verwenden. Viele gleiche Werte oder ein sortiertes Array führen dann zu einer Laufzeit von
O(n²), was in den umfangreichen Tests berücksichtigt wird.
Häufige Fragen4
Wie hoch ist die Zeitkomplexität von „Kth Largest Element in an Array“?
Das Sortieren benötigt O(n log n) Zeit. Ein Min-Heap der Größe k benötigt O(n log k) Zeit und O(k) Speicher. Quickselect mit einem zufälligen Pivot benötigt durchschnittlich O(n) Zeit und im schlimmsten Fall O(n²), was bei einem zufälligen Pivot sehr unwahrscheinlich ist.
Warum verwendet man einen Min-Heap und keinen Max-Heap, um das k-größte Element zu finden?
Der Heap speichert die k größten bisher gesehenen Werte, und der Wert, mit dem du vergleichen und den du entfernen musst, ist der kleinste davon. Ein Min-Heap hält diesen Wert ganz oben. Ein Max-Heap funktioniert nur, wenn du alle n Werte hineinlegst und k-1-mal das oberste Element entfernst, was O(n) Speicher benötigt.
Sollte ich für das k-größte Element einen Heap oder Quickselect verwenden?
Quickselect ist im Durchschnitt schneller, O(n), benötigt aber alle Werte im Speicher und ordnet sie neu. Der Heap hat eine Laufzeit von O(n log k) ohne schlechten Worst Case und funktioniert, wenn die Werte einzeln eintreffen und du sie nicht alle speichern kannst. Erkläre in einem Vorstellungsgespräch beide Verfahren und implementiere das, nach dem in der Nachfrage gefragt wird.
Kann das k-größte Element im schlimmsten Fall in linearer Zeit gefunden werden?
Ja. Die Median-of-Medians-Regel wählt ein Pivot, von dem garantiert ist, dass es einen festen Anteil der Werte abtrennt. Dadurch läuft die Selektion im schlechtesten Fall in O(n), ist in der Praxis jedoch langsamer als mit einem zufälligen Pivot. Da die Werte auf den Bereich von -10^4 bis 10^4 begrenzt sind, kannst du auch zählen, wie oft jeder Wert vorkommt, und von 10^4 abwärts gehen, bis du k Werte überschritten hast. Das dauert O(n + 2 × 10^4).
Ähnliche Aufgaben
Aufgaben mit denselben Ideen. Wer zwei oder drei davon löst, behält das Muster.
Python
def findKthLargest(nums, k):
# Schreibe hier den CodeFall 1
Fall 2
Fall 3
Eingabe
nums = [7, 2, 9, 4, 9, 1] k = 2
Erwartet
9