Найти N-е наиболее часто встречающееся число в массиве.

Find the nth most frequent number in array.
(There is no limit on the range of the numbers)

Я думаю, что мы можем

(i) сохранить вхождение каждого элемента, используя карты в C++

(ii) построить Max-кучу за линейное время появления (или частоты) элемента, а затем извлечь до N-го элемента, Каждое извлечение занимает log(n) времени для кучи.

(iii) мы получим частоту N-го наиболее часто встречающегося числа

(iv) затем мы можем линейным поиском по хешу найти элемент, имеющий эту частоту.

Время — O(NlogN) Пробел - O(N)

Есть ли лучший метод ?