Given an array **A[0…N]** I want a key value pair store which is in descending order of occurrences of element.i.e, The most occurring element appears first then second most occurring and so on.

I am waiting for someone to actually reply and giving answer to your encounters as well. *pray hard*

Here is O(nlogn) solution if you are looking for better than this I am sorry.

Just use std::pair with p.first = element and p.second = occurrence than you can use the sort function like this

sort(p,p+n,cmf)

where n = number of elements and cmf is the comparison function you have to define.

int cmf (pair < int , int > p1 , pair < int , int > p2)

{

if(p1.second>p2.second)

return 1;

else

return 0;

}

You can’t do it better than Omega(n log n) by any comparison sort including the builtin methods.