Tous les défis
Moyen 2 résolus 100.0 % de réussite

K-ième plus petit élément

Trouvez la k-ième plus petite valeur sans trier entièrement.

Ce que vous allez apprendre

  • Partitionner les valeurs autour d'un pivot
  • Ne descendre récursivement que d'un côté
  • Trouver le k-ième plus petit en temps linéaire en moyenne

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).

Entrée

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

Sortie

Retournez la k-ième plus petite valeur.

Contraintes

1 ≤ k ≤ longueur ≤ 200 000

Exemples

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

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

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

Sortie attendue :
long expected = 7;

Explication

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

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

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

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

Sortie attendue :
long expected = 5;

Explication

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

Comment l'aborder

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

Références

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

La meilleure solution validée de chaque codeur. Les plus rapides, les plus légères et les mieux notées passent devant.

# Codeur Langage Temps Mémoire Note de l'IA Solution
1 ННикита Python 811 ms - 4/5 Voir le code
2 KKKaneki Ken Python 816 ms - 3/5 Voir le code

Apprenez des autres

Solutions de la communauté

Attention spoiler : 2 solutions complètes ci-dessous Essayez d'abord de le résoudre vous-même. Vous pouvez toujours jeter un œil au code des autres développeurs et aux avis IA. Connectez-vous et résolvez le défi pour rejoindre la discussion.