1
class Solution {
2
 public:
3
  vector<int> topKFrequent(vector<int> &nums, int k) {
4
    unordered_map<int, int> map;
5
    for (int num : nums) {
6
      map[num]++;
7
    }
8

9
    vector<int> res;
10
    // pair<first, second>: first is frequency,  second is number
11
    priority_queue<pair<int, int>> pq;
12
    for (auto it = map.begin(); it != map.end(); it++) {
13
      pq.push(make_pair(it->second, it->first));
14
      if (pq.size() > (int)map.size() - k) {
15
        res.push_back(pq.top().second);
16
        pq.pop();
17
      }
18
    }
19
    return res;
20
  }
21
};