[LeetCode] Top K Frequent Elements

Top K Frequent Elements - LeetCode

Given a non-empty array of integers, return the k most frequent elements.

Example 1:

Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]

Example 2:

Input: nums = [1], k = 1
Output: [1]

 

저는 map과 priority queue를 이용해서 풀었습니다. 

map에 key, value로 값을 저장한 후 이를 value가 큰 순서대로 저장되도록 하는 priority queue에 추가합니다.

그 후 k개만큼 priority queue에서 pop 해서 answer에 추가시켜주었습니다.

 

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int, int> m;
        for (int num : nums) {
            m[num]++;
        }
        
        auto cmp = [](const auto &x, const auto &y) {
            return x.second < y.second;
        };
        
        priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(cmp)> pq(cmp);
        for (auto it = m.begin(); it != m.end(); it++) {
            pq.push(pair<int, int>(it->first, it->second));
        }
        
        vector<int> answer;
        for (int i = 0; i < k; i++) {
            answer.push_back(pq.top().first);
            pq.pop();

        }
        return answer;
    }

};