k-ésimo elemento más pequeño en la lista
Dado un total de
n enteros y un número k, se te pide encontrar el k-ésimo elemento más pequeño en la lista. Se garantiza que los elementos del arreglo son distintos.Entrada
La primera línea de la entrada contiene dos enteros
n y k (1 ≤ k ≤ n ≤ ).La siguiente línea contiene
n números enteros separados por espacio ().Salida
El programa debe mostrar el valor del k-ésimo elemento más pequeño en la lista dada.
Ejemplos
Entrada | Salida |
6 3
10 -2 4 8 3 6 | 4 |
7 2
-4 5 8 -3 10 0 7 | -3 |
Explicación
- Al ordenar la lista, se obtendría [-2, 3, 4, 6, 8, 10] ⇒ el tercer elemento más pequeño es 4
- Al ordenar la lista, se obtendría [-4, -3, 0, 5, 7, 8, 10] ⇒ el segundo elemento más pequeño es -3
Hint 1
Usa una división aleatoria similar a QuickSort.
Ordenar elementos no es factible con la restricción de tiempo dada.
Hint 2
Puedes dividir el arreglo de forma similar a QuickSort, eligiendo un pivote aleatoriamente. Luego, puedes quedarte solo con la parte necesaria del arreglo e ignorar la otra.
Este proceso puede repetirse hasta que la cantidad de elementos ignorados ANTES de tu elemento actual sea igual a
k.La división aleatoria en realidad tiene un tiempo esperado lineal . ¿Sabes por qué?
Hint 3
Cada vez que se parte el arreglo de forma aleatoria, el tamaño esperado del nuevo arreglo es la mitad del actual. Entonces, si el arreglo actual tiene un tamaño
n, después de una partición puedes descartar la mitad (n/2), tras dos particiones puedes descartar la otra mitad (n/4), y así sucesivamente. La suma de este proceso resulta en .Sin embargo, el algoritmo puede llegar a tener un comportamiento en el peor de los casos de si los pivotes aleatorios no dividen el arreglo aproximadamente en mitades.
Constraints
Time limit: 2.5 seconds
Memory limit: 512 MB
Output limit: 1 MB