Эта статья о частых элементах Leetcode 347 Top K

Вопрос

Учитывая непустой массив целых чисел, вернуть k наиболее часто встречающихся элементов

Примеры

Массив: [1, 1, 1, 2, 2, 3]; К = 2;

Ответ: [1, 2]

Подсказки

K-й элемент => найти способ сортировки элементов => приоритетная очередь/куча

частота подсчета =› хеш-карта

Предположения

K всегда допустимо, 1 ≤ K ≤ количество уникальных элементов

Решение грубой силы

Используйте хэш-карту, чтобы записать, сколько раз появляется каждый элемент => O (n)

Пройдите через хэш-карту, чтобы найти элемент с самыми высокими частотами.

=› O(m * K), где m — размер хэш-карты, а K — номер k-го элемента

Итого: О(м * К)

Оптимизация BUD (узкое место, ненужная, дублирующая работа)

Очевидно, что в решении методом перебора узким местом является процесс извлечения K-го элемента из хэш-карты. Если записи в хэш-карте можно отсортировать по их частоте, это уменьшит дублирующую работу по просмотру хэш-карты m раз.

Это приводит к методу использования приоритетной очереди или кучи:

класс freqCount {…}

класс freqComparator реализует Comparator‹freqCount›{…}

PriorityQueue‹freqCount› очередь = новая PriorityQueue‹freqCount›(размер, новая частотаComparator());

Прохождение

  1. Создайте класс freqCount и класс freqComparator для удобства.
  2. Перебрать массив и сопоставить частоту с hashMap
  3. Переберите hashMap и добавьте их в PriorityQueue.
  4. Опросить первые K элементов из PriorityQueue
  5. Всего большое O равно nlog(n), где n — длина hashMap. Вставка PriorityQueue — O(log(n))