Editorial for COCI '09 Contest 3 #3 Sort

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

By simply counting the number of times each number appears and sorting by those values we arrive at the solution. There are numerous ways we can implement that solution. To start, we can simply sort the numbers in $\mathcal O(N \log N)$ ~\mathcal O(N \log N)~ time complexity and for each comparison scan the entire sequence in $\mathcal O(N)$ ~\mathcal O(N)~ complexity.

A better solution is to precalculate all frequencies and use that data in sorting. Depending on implementation this can range from $\mathcal O(N \log^2 N)$ ~\mathcal O(N \log^2 N)~ to $\mathcal O(N \log N)$ ~\mathcal O(N \log N)~.

Comments

There are no comments at the moment.