Top K Frequent Elements

Сначала подсчитайте. Один проход с хеш-таблицей, в которой каждому значению соответствует его количество, превращает [4, 1, 4, 2, 1, 4, 3, 1, 4] в 4 → 4, 1 → 3, 2 → 1, 3 → 1.

Затем расположите различные значения в порядке ответа: сначала значение с наибольшим количеством, а при равном количестве — меньшее значение. Задайте сортировке именно такое сравнение: количество — первый ключ, значение — второй, и первые k элементов отсортированного списка будут ответом. Здесь порядок — 4, 1, 2, 3, а k = 2 оставляет 4 и 1.

Подсчёт требует O(n). Сортировка d различных значений требует O(d log d), не более O(n log n), если все значения различны: для 10^4 значений потребуется около 1.3 × 10^5 сравнений, что быстро. Недостаток в том, что сортировка упорядочивает все значения, хотя важны только первые k.

Тебе нужны только k лучших значений, поэтому храни только k кандидатов. Для каждого нового значения нужно проверить, превосходит ли оно самого слабого из хранимых кандидатов: слабее означает меньшее количество или то же количество и большее значение. Мини-куча, упорядоченная по этому правилу, держит слабейшего кандидата наверху: его можно прочитать за O(1) и заменить за O(log k).

Пройди по различным значениям. Пока в куче меньше k элементов, добавляй значение. После этого значение, которое превосходит верхний элемент, заменяет его, а значение, которое его не превосходит, отбрасывается, потому что k лучших значений уже сохранены. С библиотечной кучей короче добавлять каждое значение и извлекать элемент каждый раз, когда размер кучи превышает k: так сохраняются те же k значений.

В конце в куче будет ответ, но не в порядке ответа: куча отсортирована лишь частично. Извлечение возвращает сначала самое слабое значение, поэтому записывай ответ с последней позиции к первой.

Для каждого из d различных значений выполняется не более одной операции с кучей из k элементов, поэтому на выбор уходит O(d log k). Это быстрее сортировки, когда k намного меньше d, например при поиске 10 лучших среди 8000 различных значений.

Частота — это не любое число: это целое число от 1 до n. Это позволяет использовать сортировку по корзинам. Создайте по одной корзине для каждой частоты: в корзину c поместите значения, встречающиеся ровно c раз, а затем просматривайте корзины от корзины n вниз. Значения будут выдаваться в порядке убывания частоты, и сравнивать частоты между собой не придётся.

Правило разрешения равенства требует ещё одного условия: внутри корзины сначала должно идти меньшее значение. Значения находятся в диапазоне от -10^4 до 10^4, поэтому для подсчёта можно использовать массив из R = 2 × 10^4 + 1 счётчиков, где значение v находится по индексу v + 10^4. Пройдите по этому массиву от наименьшего значения к наибольшему и добавляйте каждое значение в корзину, соответствующую его частоте. Корзины заполняются в порядке возрастания значений — именно так, как требует правило разрешения равенства, поэтому сортировка не нужна.

Для [5, -2, 7, -2, 7, 5, 9] при проходе значения -2, 5, 7 попадут в корзину 2 именно в таком порядке, а 9 — в корзину 1. При просмотре корзин от корзины 7 первая непустая корзина — корзина 2, и k = 2 выбирает -2 и 5.

Работа алгоритма состоит из одного прохода по nums, одного прохода по R счётчикам и одного прохода по корзинам, то есть всего O(n + R): при фиксированном диапазоне значений сложность линейная. Если вместо массива счётчиков использовать хеш-таблицу, подсчёт тоже останется линейным, но корзины будут заполняться в порядке обхода хеш-таблицы, и для соблюдения правила разрешения равенства каждую из них придётся сортировать.