347. Top K Frequent Elements

Whenever the problem asks for top k numbers, it's highly likely to consider heap. This is a typical heap problem plus hash map. The hash map is used to count the frequency for each number the (key, value) pair is (number, frequency). After completing the hash map build, we build the minimal heap according the frequency. The node in heap is also a pair but this time it is (frequency, number) pair. Since we know that we only need to keep k numbers in the heap, so when the heap size is larger than k we pop out the top number. Finally, we dump all the numbers in the heap to the vector.

1:  class Solution {  
2:  public:  
3:    vector<int> topKFrequent(vector<int>& nums, int k) {  
4:      unordered_map<int, int> mp;  
5:      for (int i = 0; i < nums.size(); i++) {  
6:        mp[nums[i]]++;  
7:      }  
8:      priority_queue<pair<int, int>, vector<pair<int,int>>, greater<pair<int,int>>> minHeap;  
9:      for (auto p : mp) {  
10:        minHeap.push(make_pair(p.second, p.first));  
11:        if (minHeap.size() > k) {  
12:          minHeap.pop();  
13:        }  
14:      }  
15:      vector<int> res(k, 0);  
16:      for (int i = k-1; i >= 0; i--) {  
17:        res[i] = minHeap.top().second;  
18:        minHeap.pop();  
19:      }  
20:      return res;  
21:    }  
22:  };