Kth Largest Element in an Array

Wartość k-ta od największej jest określona przez kolejność sortowania, więc uzyskaj tę kolejność. Posortowana od największej do najmniejszej lista [7, 2, 9, 4, 9, 1] zmienia się w [9, 9, 7, 4, 2, 1], a k-ta od największej znajduje się pod indeksem k-1. Dla k = 2 jest to indeks 1, czyli druga 9. Jeśli sortowanie umieszcza najmniejsze wartości na początku, odczytaj zamiast tego indeks n-k: pod indeksem 4 w [1, 2, 4, 7, 9, 9] znajduje się ta sama 9.

Duplikaty nie wymagają specjalnego traktowania: sortowanie zachowuje każdą kopię, a każda kopia zajmuje własną pozycję.

Dla n = 10^4 sortowanie wykonuje około n log n ≈ 1.3 × 10^5 porównań, co wystarcza, by przejść wszystkie testy. Wadą jest to, że porządkuje wszystkie n wartości, mimo że liczy się tylko jedna pozycja. Dwa kolejne podejścia wykonują mniej tej pracy.

Wartość k-ta co do wielkości jest najmniejszą z k największych wartości. Przejdź więc raz przez nums i zachowuj w kopcu minimalnym tylko k największych dotąd napotkanych wartości. Szczyt kopca minimalnego to jego najmniejsza wartość, czyli dokładnie kandydat na odpowiedź.

Gdy pojawi się wartość x, a kopiec zawiera mniej niż k wartości, dodaj ją. W przeciwnym razie porównaj x z wartością na szczycie. Jeśli x nie jest większe, to co najmniej k zachowanych wartości jest nie mniejszych niż x, więc x nie może być odpowiedzią i pomijasz je. Jeśli x jest większe, wartość ze szczytu wypada z k największych: zastąp ją przez x. W przykładzie 2, dla k = 4, pierwsze cztery wartości wypełniają kopiec wartościami 5, -3, 8, 0, a na szczycie znajduje się -3. Następnie 2 jest większe niż -3 i zastępuje tę wartość, na szczycie pojawia się 0, a odpowiedzią jest 0.

Każda wartość wymaga co najwyżej jednej operacji na kopcu o złożoności O(log k), więc całość zajmuje O(n log k) czasu i O(k) pamięci. To szybsze niż sortowanie, gdy k jest małe, a rozwiązanie działa też na strumieniu: nie musisz mieć wszystkich wartości naraz. Python ma heapq, Java — PriorityQueue, C++ — priority_queue z greater, Go — container/heap, Rust — BinaryHeap z Reverse, a PHP — SplMinHeap. Kod w pozostałych językach implementuje kopiec w tablicy, gdzie dzieci indeksu i znajdują się pod indeksami 2i+1 i 2i+2 albo, w Lua i R, które indeksują od 1, pod indeksami 2i i 2i+1.

Quicksort wybiera pivot i dzieli tablicę: mniejsze wartości trafiają na jego lewo, a większe na prawo. Po jednym podziale pivot znajduje się na swoim ostatecznym indeksie w posortowanej tablicy, choć żadna z części nie jest jeszcze posortowana. Quickselect wykorzystuje ten fakt. Przy kolejności od najmniejszych do największych odpowiedź znajduje się pod indeksem target = n-k. Po podziale target znajduje się albo na lewo od pivota, albo na jego pozycji, albo na prawo od niego, więc kontynuujesz po jednej stronie i odrzucasz drugą.

Dla [7, 2, 9, 4, 9, 1] i k = 2 wartość target wynosi 6-2 = 4. Podziel tablicę względem 4: 2 i 1 zajmują indeksy 0 i 1, 4 zajmuje indeks 2, a 7, 9, 9 zajmują indeksy od 3 do 5. Indeks 4 znajduje się po prawej, więc zachowujesz tylko indeksy od 3 do 5. Podziel je względem 9: 7 zajmuje indeks 3, a obie dziewiątki zajmują indeksy 4 i 5. Pod indeksem 4 znajduje się 9, więc odpowiedzią jest 9.

Użyj podziału na trzy części: wartości mniejsze od pivota, następnie wartości równe pivotowi, a na końcu wartości większe od niego, wyznaczane przez lt i gt. Blok równych wartości [lt, gt] znajduje się już na swoim miejscu w posortowanej tablicy, więc jeśli target znajduje się w jego obrębie, możesz zakończyć. Przy zwykłym podziale na dwie części tablica zawierająca 10^4 kopii 7 zmniejsza się o jedną wartość w każdej rundzie, co daje około 5 × 10^7 kroków; wersja z podziałem na trzy części znajduje odpowiedź w jednym przebiegu.

Wybierz pivot losowo. W połowie przypadków znajdzie się on w środkowej połowie zakresu, co zmniejsza zakres do najwyżej trzech czwartych, więc oczekiwana praca to kilka przebiegów po n wartościach: O(n). Najgorszy przypadek nadal ma złożoność O(n²), jeśli każdy pivot jest skrajną wartością, a stały wybór, na przykład pierwszego elementu, prowadzi do niego dla posortowanego wejścia. Kod działa na kopii, co wymaga O(n) pamięci; podział samego nums zmniejsza to do O(1), jeśli możesz zmienić dane wejściowe.