// C++ implementation to find k numbers with most
// occurrences in the given array
#include <bits/stdc++.h>
using namespace std;
// comparison function defined for the priority queue
struct compare
{
bool operator()(pair<int, int> p1, pair<int, int> p2)
{
// if frequencies of two elements are same
// then the larger number should come first
if (p1.second == p2.second)
return p1.first < p2.first;
// insert elements in the priority queue on the basis of
// decreasing order of frequencies
return p1.second < p2.second;
}
};
// funnction to print the k numbers with most occurrences
void print_N_mostFrequentNumber(int arr[], int n, int k)
{
// unordered_map 'um' implemented as frequency hash table
unordered_map<int, int> um;
for (int i = 0; i<n; i++)
um[arr[i]]++;
// store the elements of 'um' in the vector 'freq_arr'
vector<pair<int, int> > freq_arr(um.begin(), um.end());
// priority queue 'pq' implemented as max heap on the basis
// of the comparison operator 'compare'
// element with the highest frequency is the root of 'pq'
// in case of conflicts, larger element is the root
priority_queue<pair<int, int>, vector<pair<int, int> >,
compare> pq(um.begin(), um.end());
// display the top k numbers
cout << k << " numbers with most occurrences are:\n";
for (int i = 1; i<= k; i++)
{
cout << pq.top().first << " ";
pq.pop();
}
}
// Driver program to test above
int main()
{
int arr[] = {3, 1, 4, 4, 5, 2, 6, 1};
int n = sizeof(arr) / sizeof(arr[0]);
int k = 2;
print_N_mostFrequentNumber(arr, n, k);
return 0;
}
Ly8gQysrIGltcGxlbWVudGF0aW9uIHRvIGZpbmQgayBudW1iZXJzIHdpdGggbW9zdCAKLy8gb2NjdXJyZW5jZXMgaW4gdGhlIGdpdmVuIGFycmF5IAojaW5jbHVkZSA8Yml0cy9zdGRjKysuaD4gCiAgCnVzaW5nIG5hbWVzcGFjZSBzdGQ7IAogIAovLyBjb21wYXJpc29uIGZ1bmN0aW9uIGRlZmluZWQgZm9yIHRoZSBwcmlvcml0eSBxdWV1ZSAKc3RydWN0IGNvbXBhcmUgCnsgCiAgICBib29sIG9wZXJhdG9yKCkocGFpcjxpbnQsIGludD4gcDEsIHBhaXI8aW50LCBpbnQ+IHAyKSAKICAgIHsgCiAgICAgICAgLy8gaWYgZnJlcXVlbmNpZXMgb2YgdHdvIGVsZW1lbnRzIGFyZSBzYW1lIAogICAgICAgIC8vIHRoZW4gdGhlIGxhcmdlciBudW1iZXIgc2hvdWxkIGNvbWUgZmlyc3QgCiAgICAgICAgaWYgKHAxLnNlY29uZCA9PSBwMi5zZWNvbmQpIAogICAgICAgICAgICByZXR1cm4gcDEuZmlyc3QgPCBwMi5maXJzdDsgCiAgICAgICAgICAgICAgCiAgICAgICAgLy8gaW5zZXJ0IGVsZW1lbnRzIGluIHRoZSBwcmlvcml0eSBxdWV1ZSBvbiB0aGUgYmFzaXMgb2YgCiAgICAgICAgLy8gZGVjcmVhc2luZyBvcmRlciBvZiBmcmVxdWVuY2llcyAgICAgCiAgICAgICAgcmV0dXJuIHAxLnNlY29uZCA8IHAyLnNlY29uZDsgICAgIAogICAgfSAKfTsgCiAgCi8vIGZ1bm5jdGlvbiB0byBwcmludCB0aGUgayBudW1iZXJzIHdpdGggbW9zdCBvY2N1cnJlbmNlcyAKdm9pZCBwcmludF9OX21vc3RGcmVxdWVudE51bWJlcihpbnQgYXJyW10sIGludCBuLCBpbnQgaykgCnsgCiAgICAvLyB1bm9yZGVyZWRfbWFwICd1bScgaW1wbGVtZW50ZWQgYXMgZnJlcXVlbmN5IGhhc2ggdGFibGUgCiAgICB1bm9yZGVyZWRfbWFwPGludCwgaW50PiB1bTsgCiAgICBmb3IgKGludCBpID0gMDsgaTxuOyBpKyspIAogICAgICAgIHVtW2FycltpXV0rKzsgCiAgICAgIAogICAgLy8gc3RvcmUgdGhlIGVsZW1lbnRzIG9mICd1bScgaW4gdGhlIHZlY3RvciAnZnJlcV9hcnInICAgICAgICAgCiAgICB2ZWN0b3I8cGFpcjxpbnQsIGludD4gPiBmcmVxX2Fycih1bS5iZWdpbigpLCB1bS5lbmQoKSk7IAogICAgICAKICAgIC8vIHByaW9yaXR5IHF1ZXVlICdwcScgaW1wbGVtZW50ZWQgYXMgbWF4IGhlYXAgb24gdGhlIGJhc2lzIAogICAgLy8gb2YgdGhlIGNvbXBhcmlzb24gb3BlcmF0b3IgJ2NvbXBhcmUnIAogICAgLy8gZWxlbWVudCB3aXRoIHRoZSBoaWdoZXN0IGZyZXF1ZW5jeSBpcyB0aGUgcm9vdCBvZiAncHEnIAogICAgLy8gaW4gY2FzZSBvZiBjb25mbGljdHMsIGxhcmdlciBlbGVtZW50IGlzIHRoZSByb290IAogICAgcHJpb3JpdHlfcXVldWU8cGFpcjxpbnQsIGludD4sIHZlY3RvcjxwYWlyPGludCwgaW50PiA+LCAgCiAgICAgICAgICAgICAgICAgICAgICAgICAgIGNvbXBhcmU+IHBxKHVtLmJlZ2luKCksIHVtLmVuZCgpKTsgCiAgICAgIAogICAgLy8gZGlzcGxheSB0aGUgdG9wIGsgbnVtYmVycyAKICAgIGNvdXQgPDwgayA8PCAiIG51bWJlcnMgd2l0aCBtb3N0IG9jY3VycmVuY2VzIGFyZTpcbiI7IAogICAgZm9yIChpbnQgaSA9IDE7IGk8PSBrOyBpKyspIAogICAgeyAKICAgICAgICBjb3V0IDw8IHBxLnRvcCgpLmZpcnN0IDw8ICIgIjsgCiAgICAgICAgcHEucG9wKCk7IAogICAgfSAgICAgICAgICAgICAKfSAKICAKLy8gRHJpdmVyIHByb2dyYW0gdG8gdGVzdCBhYm92ZSAKaW50IG1haW4oKSAKeyAKICAgIGludCBhcnJbXSA9IHszLCAxLCA0LCA0LCA1LCAyLCA2LCAxfTsgCiAgICBpbnQgbiA9IHNpemVvZihhcnIpIC8gc2l6ZW9mKGFyclswXSk7IAogICAgaW50IGsgPSAyOyAKICAgIHByaW50X05fbW9zdEZyZXF1ZW50TnVtYmVyKGFyciwgbiwgayk7IAogICAgcmV0dXJuIDA7IAp9IA==