K-ésimo menor elemento na lista
Dado
n inteiros e um número k, pretende-se encontrar o k-ésimo menor elemento na lista. É garantido que os elementos do array são distintos.Entrada
A primeira linha da entrada contém dois inteiros
n e k (1 ≤ k ≤ n ≤ ).A linha seguinte contém
n inteiros separados por espaço, ().Saída
O programa deve apresentar o valor do
k-ésimo menor elemento na lista dada.Exemplos
Entrada | Saída |
6 3
10 -2 4 8 3 6 | 4 |
7 2
-4 5 8 -3 10 0 7 | -3 |
Explicação
- Ao ordenar a lista, obteríamos [-2, 3, 4, 6, 8, 10]. Logo, o 3º menor elemento é 4.
- Ao ordenar a lista, obteríamos [-4, -3, 0, 5, 7, 8, 10]. Logo, o 2º menor elemento é -3.
Sugestão 1
Utilize uma partição aleatória de modo semelhante ao QuickSort.
Ordenar elementos, neste caso, não é viável dentro do limite de tempo proposto.
Sugestão 2
Pode-se particionar o array de forma semelhante ao QuickSort, escolhendo pivôs aleatoriamente. Depois disso, basta manter apenas a parte do array que interessa e ignorar a outra.
Este processo pode ser repetido até que o número de elementos ignorados ANTES do seu elemento atual seja igual a
k.A partição aleatória tem tempo de execução esperado . Consegue perceber por quê?
Sugestão 3
Cada vez que fazemos a partição do array de maneira aleatória, espera-se que o tamanho resultante do array seja aproximadamente a metade. Assim, se o array atual tem tamanho
n, depois de uma partição pode-se descartar cerca de n/2. Depois de duas particionamentos, descarta-se mais n/4, e assim por diante. Essa soma resulta em .Contudo, em pior caso, o algoritmo pode ter desempenho , caso os pivôs escolhidos aleatoriamente não resultem em partições próximas a
n/2.Constraints
Time limit: 2.5 seconds
Memory limit: 512 MB
Output limit: 1 MB