[Leetcode] 347. Top K Frequent Elements 문제 풀이

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

Top K Frequent Elements - LeetCode

문제 내용

빈도수가 높은 순서대로 k번째까지 숫자를 출력하는 문제

 

Example 1:

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

Example 2:

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

 

Constraints:

• 1 <= nums.length <= 105
• k is in the range [1, the number of unique elements in the array].
• It is guaranteed that the answer is unique.

문제 풀이

빈도수를 알기 위해 hash를 사용해서 먼저 빈도수를 구했다.

그리소 k번째 까지 순서를 알기 위해서 min heap을 사용해서 k번째까지 num을 저장하고 출력했다.

코드

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int, int> freq;
        for (auto num : nums) {
            if (freq.count(num) == 0) {
                freq[num] = 0;
            }
            freq[num]++;
        }
        
        priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> min_heap;
        for (auto f : freq) {
            if (min_heap.size() < k) {
                min_heap.emplace(f.second, f.first);
            } 
            else if (min_heap.top().first < f.second) {
                min_heap.emplace(f.second, f.first);
                min_heap.pop();
            }
        }
        
        vector<int> ans;
        while (!min_heap.empty()) {
            ans.push_back(min_heap.top().second);
            min_heap.pop();
        }
        return ans;
    }
};