[알고리즘] Top K Frequent Elements

포인트

1.  힙을 사용하여 어떤 식으로 가장 많은 것들을 받아 올 수 있는지를 확인할 수 있다.

🧶문서는 항상 수정 될 수 있습니다. 비판은 환영합니다. 

c++/cpp

#include <bits/stdc++.h>

using namespace std;

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int,int> map;
        for(int num : nums){
            map[num]++;
        }
        
        vector<int> result;
        priority_queue<pair<int,int>> pq; 

        for(auto it = map.begin(); it != map.end(); it++){
            pq.push(make_pair(it->second, it->first));
            if(pq.size() > map.size() - k){
                result.push_back(pq.top().second);
                pq.pop();
            }
        }
        return result;
    }
};

python

version1

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        return list(zip(*Counter(nums).most_common(k)))[0]

version2

class Solution:
	def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        freqs = Counter(nums)
        heaps = []
        # 힙에 음수로 삽입
        for f in freqs:
            heapq.heappush(heaps, (-freqs[f], f))

        result = []
        # k번 만큼 추출, 민 힙 이므로 가장 작은 음수 순으로 추출
        for _ in range(k):
            result.append(heapq.heappop(heaps)[1])

        return result