Find the Nth most frequent number in an array

Question

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

I think we can

(i) keep the appearance of each element using maps in C ++

(ii) construct the maximum heap in the linear occurrence time (or frequency) of the element, and then extract to the Nth element. For each extraction, log (n) time is required for heapify.

(iii) we get the frequency of the Nth most frequent number

(iv) then we can linearly search through a hash to find an element having this frequency.

Time - O (NlogN) Space - O (N)

Is there a better way?

Answer 1

Your method is basically the right one. You avoid the final hash search if you mark each vertex of the constructed heap with the number that it represents. Moreover, you can constantly monitor the fifth element of the heap when you build it, because at some point you can get to a situation where the result can no longer change, and the rest of the calculations can be discarded. But this, most likely, will not make the algorithm faster in the general case and, perhaps, not even in special cases. Therefore, you correctly answered your question.

Answer 2

This can be done in linear time and space. Let T be the total number of elements in the input array from which we must find the Nth most frequent number:

• Count and save the frequency of each number in T on the map. Let M be the total number of different elements in the array. Thus, the size of the card is M. - O (T)
• Find the Nth highest frequency on the map using the selection algorithm . - O (M)

Total time = O (T) + O (M) = O (T)

Answer 3

It depends on whether you need the most efficient or easiest to write method.

1) if you know that all numbers will be from 0 to 1000, you just create an array of 1000 zeros (arrays), go through your array and increase the correct entry position. Then you sort these occurrences and select the N-dimensional value.

2) You have a “bag” of unique items, you look at your numbers, check if this number is in the bag, if not, you add it, if it is here, you just increase the number of entries. Then you select the smallest number from it.

A bag can be a linear array, a BST, or a dictionary (hash table).

The question is " Nth most common", so I think you cannot avoid sorting (or a clever data structure), so better complexity cannot be better than O (n * log (n)).