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 | 4 |
7 2 | -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: 5 seconds
Memory limit: 512 MB
Output limit: 1 MB