Top K Frequent Elements

Najpierw zlicz wystąpienia. Jedno przejście z mapą haszującą przechowującą liczbę wystąpień każdej wartości zamienia [4, 1, 4, 2, 1, 4, 3, 1, 4] w 4 → 4, 1 → 3, 2 → 1, 3 → 1.

Następnie ułóż różne wartości w kolejności, w jakiej mają znaleźć się w odpowiedzi: najpierw większa liczba wystąpień, a przy tej samej liczbie wystąpień — mniejsza wartość. Ustaw sortowanie dokładnie według tego porównania: liczba wystąpień jako pierwsze kryterium, a wartość jako drugie. Pierwsze k elementów posortowanej listy to odpowiedź. Tutaj kolejność to 4, 1, 2, 3, a k = 2 oznacza, że zostają 4 i 1.

Zliczanie wymaga O(n). Sortowanie d różnych wartości wymaga O(d log d), a gdy każda wartość jest inna — najwyżej O(n log n): 10^4 wartości oznacza około 1.3 × 10^5 porównań, co jest szybkie. Marnotrawstwo polega na tym, że sortowanie porządkuje wszystkie wartości, choć liczy się tylko pierwsze k.

Potrzebujesz tylko k najlepszych wartości, więc przechowuj tylko k kandydatów. Dla każdej nowej wartości trzeba sprawdzić, czy jest lepsza od najsłabszego przechowywanego kandydata. Kandydat jest słabszy, gdy ma mniejszą liczność albo taką samą liczność i większą wartość. Kopiec minimum uporządkowany według tej reguły trzyma na szczycie najsłabszego kandydata, którego odczyt zajmuje O(1), a zastąpienie O(log k).

Przejdź przez różne wartości. Gdy kopiec zawiera mniej niż k elementów, dodaj wartość. Potem wartość lepsza od elementu na szczycie zastępuje go, a wartość, która nie jest lepsza, zostaje pominięta, ponieważ przechowujesz już k lepszych wartości. Korzystając z kopca dostępnego w bibliotece, możesz skrócić kod: wstawiaj każdą wartość i usuwaj element ze szczytu za każdym razem, gdy kopiec przekroczy rozmiar k. W ten sposób zachowasz te same k wartości.

Na końcu kopiec zawiera wynik, ale nie jest on uporządkowany: kopiec jest tylko częściowo posortowany. Usuwanie elementów zwraca najpierw najsłabszą wartość, więc zapisuj wynik od ostatniej pozycji do pierwszej.

Każda z d różnych wartości wymaga co najwyżej jednej operacji na kopcu zawierającym k elementów, więc wybór zajmuje O(d log k). Jest to szybsze niż sortowanie, gdy k jest dużo mniejsze niż d, na przykład przy wybieraniu 10 najlepszych spośród 8000 różnych wartości.

Licznik nie może być dowolną liczbą: jest liczbą całkowitą od 1 do n. Dzięki temu można zastosować sortowanie kubełkowe. Utwórz jeden kubełek dla każdego licznika — kubełek c będzie zawierał wartości występujące dokładnie c razy — i odczytaj kubełki, zaczynając od kubełka n. Wartości pojawią się od najczęstszych, a żadnych dwóch liczników nie trzeba porównywać.

Reguła rozstrzygania remisów wymaga jeszcze jednej rzeczy: w kubełku najpierw musi znaleźć się mniejsza wartość. Wartości mieszczą się w przedziale od -10^4 do 10^4, więc do zliczania wystarczy tablica R = 2 × 10^4 + 1 liczników, w której wartość v znajduje się pod indeksem v + 10^4. Przejdź przez tę tablicę od najmniejszej do największej wartości i dodaj każdą wartość do kubełka odpowiadającego jej licznikowi. Każdy kubełek zapełnia się w kolejności rosnącej, czyli w kolejności rozstrzygania remisów, więc nie trzeba niczego sortować.

Dla [5, -2, 7, -2, 7, 5, 9] przejście umieszcza kolejno -2, 5 i 7 w kubełku 2, a 9 w kubełku 1. Odczytując kubełki od kubełka 7 w dół, napotykamy pierwszy kubełek z wartościami — kubełek 2 — a k = 2 oznacza wybór -2 i 5.

Wykonujemy jedno przejście po nums, jedno przejście po R licznikach i jedno przejście po kubełkach, czyli łącznie O(n + R): czas liniowy dla ustalonego zakresu wartości. Jeśli zamiast tablicy zliczającej użyjesz mapy mieszającej, zliczanie nadal będzie liniowe, ale kubełki będą zapełniane w kolejności mapy i trzeba będzie posortować każdy z nich, aby zachować regułę rozstrzygania remisów.