[leetcode 347] Top K Frequent Elements

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

주어진 배열에서 가장 자주 등장하는 요소 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]

Note:

• You may assume k is always valid, 1 ≤ k ≤ number of unique elements.
• Your algorithm's time complexity must be better than O(n log n), where n is the array's size.
• It's guaranteed that the answer is unique, in other words the set of the top k frequent elements is unique.
• You can return the answer in any order.

풀이:

- c++에서 priority queue를 사용하는 문제이다. 왜냐면 정렬이 필요하기 때문

eazymean.tistory.com/99

[c++] STL priority_queue 우선순위 큐

- 맵핑으로 각 요소별 등장 횟수를 구하고 priority queue로 손쉽게 정렬한다.

 

#define pi pair<int, int>

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        
        map<int, int> m;
        for(int i=0; i<nums.size(); i++){
            m[nums[i]]++;
        }
        priority_queue<pi,vector<pi>, greater<pi>> pq;
        
        for(auto i=m.begin() ; i!=m.end() ; i++){
            pq.push({i->second,i->first});
            if(pq.size() > k){
                pq.pop();
            }
        }
        
        vector<int> answer;
        while(!pq.empty()){
            answer.push_back(pq.top().second);
            pq.pop();
        }
        return answer;
    }
    
};