Problem

[harsh4u89]

Please suggest an efficient method.
I have been asked this question in the written examination for placement in a company.

Write an program to find the top 5 most frequently occuring number in an array

[Galik]

What have you got so far?

[harsh4u89]

I used count method in the exam

But that method doesn't work if the number appears less than 50%

Max heap can be used for this.

[Galik]

Well I can't say if this is the most efficient method. But it make heavy use of the standard libs so its probably not too bad:

#include <set>
#include <iostream>
#include <algorithm>
#include <ctime>
#include <cstdlib>

// Duplicate range
typedef std::pair<int*, int*> dups;

// Sort multiset based on number of duplicates
struct fewer
{
	bool operator()(const dups& a, const dups& b)
	{
		return a.second - a.first < b.second - b.first;
	}
};

typedef std::multiset<dups, fewer> dupset;
typedef std::multiset<dups, fewer>::reverse_iterator riter;

void top_freq(int* array, int size, int number)
{
	dupset sorted;

	int* i = array;
	int* end = array + size;

	// Sort array to make duplicates adjacent
	std::sort(i, end);

	// Put duplicate ranges into multiset
	dups p;
	while(i != end)
	{
		p = std::equal_range(i, end, *i);
		sorted.insert(p);
		i = p.second;
	}

	// Output the top number of elements
	riter r = sorted.rbegin();
	for(int i = 0; r != sorted.rend() && i < number; ++r, ++i)
	{
		std::cout << *r->first << " has " << (r->second - r->first) << '\n';
	}
}

const int SIZE = 1024;

int main()
{
	srand(time(0));
	int array[SIZE];

	for(int i = 0; i < SIZE; ++i)
	{
		array[i] = rand() % 100;
	}

	top_freq(array, SIZE, 5);
}