k-ième plus petit élément dans la liste
Étant donné
n entiers et un nombre k, vous devez déterminer le k-ième plus petit élément de la liste. On garantit que les éléments du tableau sont distincts.Entrée
La première ligne de l’entrée contient deux entiers
n et k (1 ≤ k ≤ n ≤ ).La ligne suivante contient
n entiers séparés par des espaces ().Sortie
Le programme doit afficher la valeur du k-ième plus petit élément dans la liste.
Exemples
Entrée | Sortie |
6 3
10 -2 4 8 3 6 | 4 |
7 2
-4 5 8 -3 10 0 7 | -3 |
Explication
- La liste triée serait [-2, 3, 4, 6, 8, 10] ⇒ le troisième plus petit élément est 4
- La liste triée serait [-4, -3, 0, 5, 7, 8, 10] ⇒ le deuxième plus petit élément est -3
Indice 1
Utilisez un partitionnement aléatoire similaire à QuickSort.
Trier éléments n’est pas envisageable dans cette limite de temps.
Indice 2
Vous pouvez partitionner le tableau de manière similaire à QuickSort en choisissant un pivot aléatoire. Ensuite, vous ne conservez que la partie du tableau dont vous avez réellement besoin et ignorez le reste.
Ce processus peut être répété jusqu’à ce que le nombre d’éléments ignorés AVANT l’élément recherché soit égal à
k.Le partitionnement aléatoire offre un temps d’exécution linéaire moyen . Savez-vous pourquoi ?
Indice 3
Chaque fois que le tableau est partitionné aléatoirement, la taille attendue de la partie résultante est la moitié du tableau courant. Ainsi, si le tableau a une taille de
n, après un premier partitionnement, vous pouvez écarter n/2 éléments, puis n/4 après le suivant, et ainsi de suite. Cette somme aboutit à.
Constraints
Time limit: 2.5 seconds
Memory limit: 512 MB
Output limit: 1 MB