Todos los desafíos
Intermedio 2 resueltos 100.0% de aceptación

K-th Smallest Element

Find the k-th smallest value without fully sorting.

Lo que aprenderás

  • Partir los valores alrededor de un pivote
  • Hacer recursión solo hacia un lado
  • Encontrar el k-ésimo menor en tiempo lineal promedio

Problema

Return the k-th smallest value of the list (k counts from 1). Quickselect finds it in average O(n) time without sorting everything.

Implement kth_smallest(numbers, k).

Input

numbers: The list of integers. k: Which smallest value to return, starting at 1.

Output

Return the k-th smallest value.

Restricciones

1 ≤ k ≤ length ≤ 200,000

Ejemplos

Ejemplo 1
Entrada:
numbers = [7, 10, 4, 3, 20, 15]
k = 3

Salida esperada:
expected = 7
Entrada:
std::vector<long long> numbers = {7, 10, 4, 3, 20, 15};
long long k = 3;

Salida esperada:
long long expected = 7;
Entrada:
long[] numbers = new long[] {7, 10, 4, 3, 20, 15};
long k = 3;

Salida esperada:
long expected = 7;

Explicación

Sorted: 3, 4, 7, 10, 15, 20; the 3rd smallest is 7.

Ejemplo 2
Entrada:
numbers = [5, 5, 1]
k = 2

Salida esperada:
expected = 5
Entrada:
std::vector<long long> numbers = {5, 5, 1};
long long k = 2;

Salida esperada:
long long expected = 5;
Entrada:
long[] numbers = new long[] {5, 5, 1};
long k = 2;

Salida esperada:
long expected = 5;

Explicación

Sorted: 1, 5, 5; the 2nd smallest is 5 (duplicates count).

Cómo abordarlo

Inténtalo primero por tu cuenta y luego abre las pistas una a una.

Pista 1

Solo necesitas el elemento que quedaría en la posición k al ordenar, no la lista completamente ordenada.

Pista 2

Particiona alrededor de un pivote y recurre o itera solo hacia el lado que aún puede contener el rango buscado.

Pista 3

Recuerda que k es uno-basado, y los duplicados también cuentan como posiciones separadas.

Complejidad esperada

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

Referencias

Este reto está adaptado para CodeUtility. Sigue el enunciado y las restricciones indicadas arriba.

Clasificación

Clasificación completa

La mejor solución aprobada de cada programador. Las más rápidas, ligeras y mejor valoradas van primero.

# Programador Lenguaje Tiempo Memoria Revisión de IA Solución
1 ННикита Python 811 ms - 4/5 Ver código
2 KKKaneki Ken Python 816 ms - 3/5 Ver código

Aprende de otros

Soluciones de la comunidad

Alerta de spoiler: 2 soluciones completas abajo Intenta resolverlo tú mismo primero. Igual puedes ver el código de otros desarrolladores y las reseñas de IA. Inicia sesión y resuelve el reto para unirte a la discusión.