Das k-kleinste Element in der Liste
Gegeben sind
n Ganzzahlen und eine Zahl k. Gesucht ist das k-kleinste Element in der Liste. Es ist garantiert, dass alle Elemente im Array verschieden sind.Eingabe
Die erste Zeile der Eingabe enthält zwei ganze Zahlen
n und k (1 ≤ k ≤ n ≤ ).Die zweite Zeile enthält
n durch Leerzeichen getrennte ganze Zahlen ().Ausgabe
Das Programm soll den Wert des k-kleinsten Elements in der gegebenen Liste ausgeben.
Beispiele
Eingabe | Ausgabe |
6 3
10 -2 4 8 3 6 | 4 |
7 2
-4 5 8 -3 10 0 7 | -3 |
Erklärung
- Die sortierte Liste wäre [-2, 3, 4, 6, 8, 10] ⇒ Das 3. kleinste Element ist 4.
- Die sortierte Liste wäre [-4, -3, 0, 5, 7, 8, 10] ⇒ Das 2. kleinste Element ist -3.
Hinweis 1
Verwenden Sie ein zufälliges Partitionieren (random partitioning) ähnlich wie bei QuickSort.
Das Sortieren von Elementen ist in diesem Zeitlimit nicht umsetzbar.
Hinweis 2
Man kann das Array ähnlich wie bei QuickSort mit einem zufällig gewählten Pivot partitionieren. Danach wird nur der Teil des Arrays weiter betrachtet, der tatsächlich benötigt wird; der andere Teil wird verworfen.
Dieser Vorgang wird so lange wiederholt, bis die Anzahl der verworfenen Elemente VOR dem gesuchten Wert genau
k entspricht.Zufälliges Partitionieren erreicht tatsächlich eine erwartete lineare Laufzeit . Wissen Sie warum?
Hinweis 3
Bei jeder zufälligen Partitionierung wird im Durchschnitt davon ausgegangen, dass etwa die Hälfte des aktuellen Arrays wegfällt. Hat das aktuelle Array also die Größe
n, kann nach einer Partitionierung n/2 verworfen werden, nach zwei Partitionierungen n/4 und so weiter. Summiert ergibt das .Allerdings kann das Verfahren im schlimmsten Fall eine Laufzeit von erreichen, nämlich wenn die zufällig gewählten Elemente das Array nicht wie erwartet halbieren.
Constraints
Time limit: 2.5 seconds
Memory limit: 512 MB
Output limit: 1 MB