Почему это работает
- Куча — те же k наибольших, но с другим ключом: она сравнивает, как часто встречаются числа, а не сами числа. Поэтому уходит 9, самое большое число, — оно самое редкое.
- Каждое разное число проходит через кучу один раз, и как только их k + 1, уходит самое редкое. Поэтому до конца остаются k самых частых.
- В куче не больше k + 1 чисел, поэтому при большом числе разных значений это дешевле, чем сортировать их все по счётчику.
Сложность
Время O(n + m log k): один проход, чтобы посчитать n чисел, затем m разных чисел через кучу не больше чем из k + 1. Память O(m) на счётчики.
дальшеТеперь реши её сам, без подсказок.
Решить на LeetCode ↗