Середина
Проблема
Учитывая непустой массив целых чисел, верните 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).