A abordagem mais simples para encontrar o K-ésimo menor número em uma lista é ordenar toda a lista e acessar o elemento na posição K. No entanto, este método geralmente ultrapassa o limite de tempo, especialmente para grandes entradas. Neste artigo, exploraremos abordagens mais eficientes para resolver este problema.

Uma das primeiras ideias foi usar estruturas de dados como montes (heaps) para evitar a ordenação completa da lista. A ideia é construir um heap e extrair elementos um por um até encontrar o K-ésimo menor número. Apesar disso, o código inicial teve problemas de desempenho, possivelmente devido à implementação do heap.

#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <algorithm>

void trocar(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

void rearrangeHeap(int* Numeros, int indice, int ultimo) {
    int max = indice;
    if (2 * indice <= ultimo) {
        max = 2 * indice;
        if (2 * indice + 1 <= ultimo && Numeros[max] < Numeros[2 * indice + 1])
            max = 2 * indice + 1;
        if (Numeros[max] < Numeros[indice]) {
            trocar(Numeros + indice, Numeros + max);
            rearrangeHeap(Numeros, max, ultimo);
        }
    }
}

int extrair(int* Numeros, int* ultimo) {
    int temp = Numeros[1];
    int now = Numeros[*ultimo];
    Numeros[1] = now;
    rearrangeHeap(Numeros, 1, *ultimo - 1);
    (*ultimo)--;
    return temp;
}

int main() {
    int n, k;
    scanf("%d %d", &n, &k);
    int* Numeros = (int*)malloc(n * sizeof(int));
    for (int i = 0; i < n; i++)
        scanf("%d", Numeros + i);
    
    for (int i = n / 2; i >= 1; i--)
        rearrangeHeap(Numeros, i, n);
    
    int resultado;
    for (int i = 1; i <= k + 1; i++)
        resultado = extrair(Numeros, &n);
    
    printf("%d", resultado);
    return 0;
}

Apesar das melhorias, o código ainda apresentava problemas de desempenho. A solução final surgiu ao substituir as funções de entrada/saída do C++ (cin e cout) pelas mais rápidas funções do C (scanf e printf), que melhoraram significativamente o desempenho.

Uma abordagem mais eficiente é usar a técnica de divisão e conquista, similar ao algoritmo de quicksort, para encontrar o K-ésimo menor número sem ordenar toda a lista. Este método reduz drasticamente o tempo de execução.

#include <stdio.h>
#include <stdlib.h>

void trocar(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

int encontrarK(int* Numeros, int inicio, int fim, int k) {
    int pivo = Numeros[inicio];
    int left = inicio;
    int right = fim;
    
    while (left < right) {
        while (Numeros[right] >= pivo && left < right)
            right--;
        while (Numeros[left] <= pivo && left < right)
            left++;
        trocar(Numeros + left, Numeros + right);
    }
    
    trocar(Numeros + left, Numeros + inicio);
    
    if (k > left)
        return encontrarK(Numeros, left + 1, fim, k);
    else if (k < left)
        return encontrarK(Numeros, inicio, left - 1, k);
    else
        return Numeros[k];
}

int main() {
    int n, k;
    scanf("%d %d", &n, &k);
    int* Numeros = (int*)malloc(n * sizeof(int));
    for (int i = 0; i < n; i++)
        scanf("%d", Numeros + i);
    
    printf("%d", encontrarK(Numeros, 0, n - 1, k));
    return 0;
}

Esta abordagem utiliza a divisão e conquista para localizar rapidamente o K-ésimo menor número, com uma complexidade de tempo O(n) em média, comparado ao O(n log n) da ordenação tradicional.