How to arrange an array in decreasing order of frequency of each number?

Question

Input : {5, 13, 6, 5, 13, 7, 8, 6, 5}

Output : {5, 5, 5, 13, 13, 6, 6, 7, 8}

The question is to arrange the numbers in the array in decreasing order of their frequency, preserving the order of their occurrence.

If there is a tie, like in this example between 13 and 6, then the number occurring first in the input array would come first in the output array.

Answer 1

I guess I'd do it like this:

Use a key-value data structure where the number itself is the key and the occurrence count and first occurrence index are the value.

Now traverse all numbers. If the number is not yet known (in the data structure), add it, remembering the current index as well as 1 as count. Otherwise, increment the count.

Now sort the data structure contents by the occurrence count (decreasing) and the occurrence index (increasing), and output the result (repeating the number using the occurrence count).

Processing space used <= N, time used depending on data structure and dictionary would probably be about O(N log N)