Середина

Проблема

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

Пример 1:

Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]

Пример 2:

Input: nums = [1], k = 1
Output: [1]

Примечание.

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

Решение

Используйте хэш-карту, чтобы сохранить счетчики всех чисел, и используйте кучу, чтобы получить k наибольших чисел.

Сложность

Для подсчета чисел и вставки в хэш-карту в среднем / худшем случае требуется O (n) / O (nlogn) времени. Затем требуется O (n) времени для создания кучи и O (klogn) времени, чтобы вытолкнуть k самых больших элементов. Следовательно, его временная сложность составляет O (n + n + klogn) / O (nlogn + n + klogn) = O (n + klogn) / O ((n + k) logn). в среднем / худшем случаях.

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