[LeetCode] 347. Top K Frequent Elements

https://leetcode.com/problems/top-k-frequent-elements/description/

Top K Frequent Elements - LeetCode

문제 유형 : 해시, 힙

문제 난이도 : Medium

 

문제

Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.

nums배열과 k정수가 주어진다. k등만큼 많은 요소를 반환해라. 순서는 상관없다.

 

풀이

map(key, value)를 사용하여 우선순위 큐에 넣고 k등까지만 저장하여 반환하면 된다. value로 비교를 한다.

 

코드(C++)

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 pair<int, int>& a, const pair<int, int>& b) {
            return a.second > b.second;
        };
        priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(cmp)> pq(cmp);
        for (const auto& entry : m) {
            pq.push(entry);
            if (pq.size() > k) {
                pq.pop();
            }
        }

        vector<int> result;
        while (!pq.empty()) {
            result.push_back(pq.top().first);
            pq.pop();
        }
        return result;
    }

};