Дан массив из n элементов. Найдите k самых часто встречающихся. Почему полная сортировка — не лучший ответ и какие есть варианты быстрее?

Основной ответ

Шаг один — Counter: частоты за O(n) времени и O(u) памяти, где u — число уникальных значений. Шаг два — выбор k лучших. Полная сортировка пар даёт O(u log u) и сортирует всё ради k элементов. Мин-куча размера k: кладём первые k пар, дальше сравниваем частоту с вершиной (минимумом среди лучших) и при превышении делаем замену — O(u log k), память O(k). Именно мин-куча, а не макс-: нам нужно быстро находить слабейшего из текущих лидеров. Bucket sort использует то, что частота не превышает n: раскладываем значения по корзинам «частота → элементы» и собираем с конца — O(n) времени и памяти. Quickselect по частотам — O(u) в среднем. Куча незаменима для потока: хранит O(k) и обновляется на лету.

Ключевые моменты

• Мин-куча для топа. Вершина кучи — слабейший из k лидеров; новый кандидат сравнивается только с ним, замена стоит O(log k).
• Bucket sort. Частоты лежат в диапазоне 1..n, значит применима сортировка подсчётом по частоте — линейное время без куч.
• Quickselect. Среднее O(n), но худший случай квадратичен и результат не упорядочен; упоминать как альтернативу с оговорками.
• Потоковый сценарий. При данных, не влезающих в память, или бесконечном потоке куча размера k — стандартный ответ; точный подсчёт частот потока — отдельная задача (count-min sketch).

Практический контекст

Задача различает уровни: джуниор сортирует, миддл знает кучу и её сложность, сеньор сравнивает кучу, bucket sort и quickselect и выбирает по контексту. Уточните: нужен ли порядок внутри топ-k, как разрешать равные частоты, одноразовый массив или поток, сколько уникальных элементов. В Python уместно показать heapq.nlargest — и сказать, что у него внутри та же куча размера k.

Пример кода

import heapq
from collections import Counter

def top_k_frequent(nums, k):
    counts = Counter(nums)  # O(n)
    heap = []  # мин-куча из (частота, элемент), размер <= k
    for value, freq in counts.items():
        if len(heap) < k:
            heapq.heappush(heap, (freq, value))
        elif freq > heap[0][0]:
            heapq.heapreplace(heap, (freq, value))
    return sorted((v for _, v in heap),
                  key=lambda v: -counts[v])

assert top_k_frequent([1, 1, 1, 2, 2, 3], 2) == [1, 2]
assert top_k_frequent([4], 1) == [4]
assert top_k_frequent([5, 5, 6, 6, 7], 2) == [5, 6]

Частые ошибки

• Сразу сортируют все частоты и не могут предложить ничего лучше O(n log n)
• Берут макс-кучу на все элементы вместо мин-кучи размера k, теряя выигрыш по памяти
• Забывают, что частота ограничена n, и не находят линейный bucket sort