L'elemento k-esimo più piccolo nella lista
Dato un elenco di
n interi e un numero k, il tuo compito è trovare l'elemento k-esimo più piccolo nella lista. Si garantisce che gli elementi dell'array siano tutti distinti.Input
La prima riga dell’input contiene due interi
n e k (1 ≤ k ≤ n ≤ ).La riga successiva contiene
n numeri interi separati da spazi ().Output
Il programma deve restituire il valore dell’elemento k-esimo più piccolo nella lista fornita.
Esempi
Input | Output |
6 3
10 -2 4 8 3 6 | 4 |
7 2
-4 5 8 -3 10 0 7 | -3 |
Spiegazione
- Dopo aver ordinato la lista, si otterrebbe [-2, 3, 4, 6, 8, 10] ⇒ il 3° elemento più piccolo è 4
- Dopo aver ordinato la lista, si otterrebbe [-4, -3, 0, 5, 7, 8, 10] ⇒ il 2° elemento più piccolo è -3
Suggerimento 1
Usa un partizionamento casuale (random partitioning) simile a QuickSort.
Ordinare elementi non è consigliabile a causa dei limiti di tempo.
Suggerimento 2
Puoi partizionare l’array in modo simile a QuickSort, scegliendo un pivot a caso. In seguito, puoi mantenere solo la parte dell’array necessaria e ignorare quella non necessaria.
Questo processo può essere ripetuto finché il numero di elementi scartati PRIMA dell’elemento corrente non è uguale a
k.Il partizionamento casuale ha un tempo di esecuzione atteso pari a . Ti sei chiesto perché?
Suggerimento 3
Ogni volta che partizioni l’array in modo casuale, la dimensione attesa della parte rimanente è la metà di quella corrente. Quindi, se l’array corrente ha dimensione
n, dopo una partizione puoi scartarne metà (n/2), dopo due partizioni puoi scartarne un’altra metà (n/4) e così via. Questa somma risulta essere .Tuttavia, l’algoritmo può raggiungere nel peggiore dei casi prestazioni di tipo qualora le scelte casuali del pivot non producano la partizione sperata di dimensione
n/2.Constraints
Time limit: 2.5 seconds
Memory limit: 512 MB
Output limit: 1 MB