Top K Frequent Elements

Средняя№347k наибольших

Дан массив целых чисел и число k. Нужно вернуть k чисел, которые встречаются чаще всего, в любом порядке; ответ всегда однозначный. Наш пример: [9, 1, 9, 4, 1, 4, 1, 4] и k = 2 — ответ [4, 1]: 4 и 1 встречаются по 3 раза, а 9 — только 2.

347 Top K Frequent ElementsРазбор · 1×

Пример: [9, 1, 9, 4, 1, 4, 1, 4], k = 2. Сверху — числа; под ними — счётчики; ниже — мин-куча по счётчику, счётчик под каждым числом.

91941414count—мин-кучапо счётчику
ещё не посчитанотекущее xпосчитано; в кучекорень: самое редкое в кучевыброшеноответ

Пока ничего не посчитано: count = {}

01/29
сначала · назад · пуск · шаг
Скорость
1function topKFrequent(nums, k):
2 count = empty map // missing keys: 0
3 for each x in nums:
4 count[x] = count[x] + 1
5 heap = empty min-heap // ordered by count[x]
6 for each x in keys of count:
7 push x into heap
8 if size of heap > k:
9 pop min from heap // the rarest
10 return heap
состояние
count
{}
x
–
heap
–
историянажмите шаг, чтобы вернуться

← → шаг · пробел — пауза

Почему это работает

  1. Куча — те же k наибольших, но с другим ключом: она сравнивает, как часто встречаются числа, а не сами числа. Поэтому уходит 9, самое большое число, — оно самое редкое.
  2. Каждое разное число проходит через кучу один раз, и как только их k + 1, уходит самое редкое. Поэтому до конца остаются k самых частых.
  3. В куче не больше k + 1 чисел, поэтому при большом числе разных значений это дешевле, чем сортировать их все по счётчику.

Сложность

Время O(n + m log k): один проход, чтобы посчитать n чисел, затем m разных чисел через кучу не больше чем из k + 1. Память O(m) на счётчики.

дальшеТеперь реши её сам, без подсказок.

Решить на LeetCode ↗

Задача и её условие принадлежат LeetCode. Здесь — наш пересказ, наш пример и наше решение. Patterns Hero не связан с LeetCode.