Leetcode - 347. Top K Frequent Elements

- Heap을 사용해 풀이하는 문제 중 Top k 유형의 문제

- 풀이법

k best 요소를 찾는 문제. 가장 쉬운 해결법: 정렬 후 top k 요소 리턴하는 것. 시간복잡도: O(n log n)

Heap을 사용하면 k < n일 때 O(n log k)로 해결 가능.

문제의 조건에 따라 heap에 요소를 넣은 뒤, k만큼 poll하고 답을 return.

heap 처리는 최악의 경우 O(log k)이며 n만큼 반복했기 때문에 O(n log k)

 

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

 

 

Top K Frequent Elements - LeetCode

 

 

 

 

- 문제

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

 

- 답

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int n : nums) {
            map.put(n, map.getOrDefault(n, 0) + 1);
        }
        
        PriorityQueue<Integer> pq = new PriorityQueue<>((n1, n2) -> map.get(n1) - map.get(n2));
        
        for (int num : map.keySet()) {
            pq.add(num);
            if (pq.size() > k) {
                pq.poll();
            }
        }
        
        int[] ans = new int[k];
        for (int i = 0; i < k; i++) {
            ans[i] = pq.poll();
        }
        
        return ans;
    }
}