Kth Largest Element in an Array

O k-ésimo maior valor é definido pela ordem de classificação, então produza essa ordem. Em ordem decrescente, [7, 2, 9, 4, 9, 1] se torna [9, 9, 7, 4, 2, 1], e o k-ésimo maior fica no índice k-1. Para k = 2, esse é o índice 1, o segundo 9. Se sua ordenação colocar o menor primeiro, leia o índice n-k: o índice 4 de [1, 2, 4, 7, 9, 9] é o mesmo 9.

Duplicatas não exigem nenhum tratamento especial: a ordenação mantém cada cópia, e cada cópia ocupa sua própria posição.

Com n = 10^4, uma ordenação faz cerca de n log n ≈ 1.3 × 10^5 comparações, o que passa em todos os testes. O desperdício está em colocar todos os n valores em ordem quando apenas uma posição importa. As próximas duas abordagens fazem menos desse trabalho.

O k-ésimo maior valor é o menor dos k maiores valores. Então percorra nums uma vez e mantenha apenas os k maiores valores vistos até o momento em um min-heap. O topo de um min-heap é seu menor valor, que é exatamente o candidato à resposta.

Quando um valor x chega e o heap contém menos de k valores, adicione-o. Caso contrário, compare x com o topo. Se x não for maior, pelo menos k valores que você manteve são maiores ou iguais a x, então x nunca poderá ser a resposta e você o ignora. Se x for maior, o topo deixou de fazer parte dos k maiores: substitua-o por x. No exemplo 2, com k = 4, os quatro primeiros valores preenchem o heap com 5, -3, 8, 0 e o topo é -3. Então 2 supera -3 e o substitui, o topo passa a ser 0, e 0 é a resposta.

Cada valor exige no máximo uma operação de heap de O(log k), então o total é de O(n log k) de tempo e O(k) de memória. Isso é melhor do que ordenar quando k é pequeno e funciona em um fluxo: você nunca precisa de todos os valores ao mesmo tempo. Python tem heapq, Java tem PriorityQueue, C++ tem priority_queue com greater, Go tem container/heap, Rust tem BinaryHeap com Reverse e PHP tem SplMinHeap. O código para as outras linguagens implementa o heap em um array, no qual os filhos do índice i ficam em 2i+1 e 2i+2, ou em 2i e 2i+1 em Lua e R, que contam a partir de 1.

O Quicksort escolhe um pivô e particiona: valores menores à esquerda dele, valores maiores à direita. Após uma partição, o pivô fica em seu índice final na ordenação, embora nenhum dos lados esteja ordenado ainda. O Quickselect usa esse fato. Na ordem do menor para o maior, a resposta está no índice target = n-k. Após uma partição, target está à esquerda do pivô, no pivô ou à direita dele, então você continua em um dos lados e descarta o outro.

Para [7, 2, 9, 4, 9, 1] e k = 2, target é 6-2 = 4. Particione em torno de 4: 2 e 1 ficam nos índices 0 e 1, 4 fica no índice 2, e 7, 9, 9 ficam nos índices 3 a 5. O índice 4 está à direita, então você mantém apenas os índices 3 a 5. Particione esses valores em torno de 9: 7 fica no índice 3 e os dois 9s ficam nos índices 4 e 5. O índice 4 contém um 9, então a resposta é 9.

Use uma partição em três vias: valores menores que o pivô, depois valores iguais a ele e, por fim, valores maiores que ele, acompanhados por lt e gt. O bloco de valores iguais [lt, gt] já está em sua posição ordenada, então, se target estiver dentro dele, você terminou. Com uma partição simples em duas vias, um array de 10^4 cópias de 7 diminui em um valor por rodada, cerca de 5 × 10^7 passos; a versão em três vias resolve isso em uma passagem.

Escolha o pivô aleatoriamente. Em metade das vezes, ele cai na metade central do intervalo, o que reduz o intervalo para no máximo três quartos do tamanho anterior. Assim, o trabalho esperado corresponde a algumas passagens pelos n valores: O(n). O pior caso ainda é O(n²) se todo pivô for um valor extremo, e uma escolha fixa, como o primeiro elemento, resulta nesse caso quando a entrada está ordenada. O código trabalha sobre uma cópia, o que custa O(n) de memória; particionar o próprio nums reduz esse custo para O(1) se você puder alterar a entrada.