K-ième plus petit élément

Problème

Retournez la k-ième plus petite valeur de la liste (k commence à 1). Quickselect la trouve en temps moyen O(n) sans tout trier.

Implémentez kth_smallest(numbers, k).

numbers : La liste d'entiers. k : Quelle plus petite valeur retourner, en commençant à 1.

Retournez la k-ième plus petite valeur.

1 ≤ k ≤ longueur ≤ 200 000

Exemple 1

Entrée :
k = 3
numbers = [7, 10, 4, 3, 20, 15]

Sortie attendue :
expected = 7

Entrée :
long long k = 3;
std::vector<long long> numbers = {7, 10, 4, 3, 20, 15};

Sortie attendue :
long long expected = 7;

Entrée :
long k = 3;
long[] numbers = new long[] {7, 10, 4, 3, 20, 15};

Sortie attendue :
long expected = 7;

Trié : 3, 4, 7, 10, 15, 20 ; la 3ᵉ plus petite est 7.

Exemple 2

Entrée :
k = 2
numbers = [5, 5, 1]

Sortie attendue :
expected = 5

Entrée :
long long k = 2;
std::vector<long long> numbers = {5, 5, 1};

Sortie attendue :
long long expected = 5;

Entrée :
long k = 2;
long[] numbers = new long[] {5, 5, 1};

Sortie attendue :
long expected = 5;

Trié : 1, 5, 5 ; la 2ᵉ plus petite est 5 (les doublons comptent).

Essayez d'abord seul, puis ouvrez les indices un par un.

Indice 1

Tu n’as besoin que de l’élément qui se trouverait en position k après tri, pas de la liste entièrement triée.

Indice 2

Partitionne autour d’un pivot et recurse ou itère seulement du côté qui peut encore contenir le rang cible.

Indice 3

Souviens-toi que k est basé sur 1, et que les doublons comptent quand même comme des positions distinctes.

Complexité attendue

O(n) average time, O(1) extra space

Ce défi a été adapté pour CodeUtility. Suivez l'énoncé et les contraintes ci-dessus.