fork download
  1. // C++ implementation to find k numbers with most
  2. // occurrences in the given array
  3. #include <bits/stdc++.h>
  4.  
  5. using namespace std;
  6.  
  7. // comparison function defined for the priority queue
  8. struct compare
  9. {
  10. bool operator()(pair<int, int> p1, pair<int, int> p2)
  11. {
  12. // if frequencies of two elements are same
  13. // then the larger number should come first
  14. if (p1.second == p2.second)
  15. return p1.first < p2.first;
  16.  
  17. // insert elements in the priority queue on the basis of
  18. // decreasing order of frequencies
  19. return p1.second < p2.second;
  20. }
  21. };
  22.  
  23. // funnction to print the k numbers with most occurrences
  24. void print_N_mostFrequentNumber(int arr[], int n, int k)
  25. {
  26. // unordered_map 'um' implemented as frequency hash table
  27. unordered_map<int, int> um;
  28. for (int i = 0; i<n; i++)
  29. um[arr[i]]++;
  30.  
  31. // store the elements of 'um' in the vector 'freq_arr'
  32. vector<pair<int, int> > freq_arr(um.begin(), um.end());
  33.  
  34. // priority queue 'pq' implemented as max heap on the basis
  35. // of the comparison operator 'compare'
  36. // element with the highest frequency is the root of 'pq'
  37. // in case of conflicts, larger element is the root
  38. priority_queue<pair<int, int>, vector<pair<int, int> >,
  39. compare> pq(um.begin(), um.end());
  40.  
  41. // display the top k numbers
  42. cout << k << " numbers with most occurrences are:\n";
  43. for (int i = 1; i<= k; i++)
  44. {
  45. cout << pq.top().first << " ";
  46. pq.pop();
  47. }
  48. }
  49.  
  50. // Driver program to test above
  51. int main()
  52. {
  53. int arr[] = {3, 1, 4, 4, 5, 2, 6, 1};
  54. int n = sizeof(arr) / sizeof(arr[0]);
  55. int k = 2;
  56. print_N_mostFrequentNumber(arr, n, k);
  57. return 0;
  58. }
Success #stdin #stdout 0s 5276KB
stdin
Standard input is empty
stdout
2 numbers with most occurrences are:
4 1