Skip to content

Instantly share code, notes, and snippets.

@SuryaPratapK
Created January 28, 2021 20:34
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save SuryaPratapK/8e6f0750cc1d001e7fedb7cd2d5c0380 to your computer and use it in GitHub Desktop.
Save SuryaPratapK/8e6f0750cc1d001e7fedb7cd2d5c0380 to your computer and use it in GitHub Desktop.
class Solution {
struct node{
int no;
int freq;
node(int a,int b) //Constructor for value initialization for each node
{
no = a;
freq = b;
}
};
struct compare { //Maintains MAX-HEAP based on frequency
bool operator()(node const& a, node const& b)
{
return a.freq < b.freq;
}
};
public:
vector<int> topKFrequent(vector<int>& nums, int k) {
unordered_map<int,int> m; //Key->Number...Value->Freq
//STEP-1: Store frequency of all elements in map
for(int ele: nums)
m[ele]+=1;
//STEP-2: Now build a heap
priority_queue<node,vector<node>,compare> heap; //Compare defines a max-heap based on frequency
for(auto it: m)
heap.push(node(it.first,it.second));
vector<int> ans; //Stores top-K elements
//STEP-3: Pop top-k elemnts and store the numbers in ans vector
while(k--)
{
node temp = heap.top();
heap.pop();
ans.push_back(temp.no);
}
return ans;
}
};
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment