[LeetCode] 347. Top K Frequent Elements - 아이디어(Idea) + 해시맵(HashMap) + 우선순위큐(PriorityQueue) JAVA

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

코드설명

아이디어(Idea) + 해시맵(HashMap) + 우선순위큐(PriorityQueue) 을 활용합니다.

 

방법은, 

1. HashMap으로 각 숫자별 Frequency를 구합니다.

2. 각 Frequency별로 정렬을 하거나 배열을 활용하여서 값을 만들고 Frequency가 높은순서대로 k개 뽑습니다. (배열 활용시 nums.length개의 빈도수만 가능하다는 점을 활용합니다.)

코드

정답코드1입니다.

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        HashMap<Integer, Integer> hashmap = new HashMap<>();
        for(int v : nums){
            hashmap.put(v, hashmap.getOrDefault(v, 0) + 1);
        }

        List<Integer>[] list = new ArrayList[nums.length + 1];
        for(int i=0; i<=nums.length; i++){
            list[i] = new ArrayList<Integer>();
        }
        for(Map.Entry<Integer, Integer> entrySet : hashmap.entrySet()){
            list[entrySet.getValue()].add(entrySet.getKey());
        }

        int[] answer = new int[k];
        int idx = 0;
        for(int i=nums.length; i>=0; i--){
            List<Integer> connected = list[i];
            for(int j=0; j<connected.size(); j++){
                answer[idx++] = connected.get(j);
                if(idx == k) return answer;
            }
        }

        return answer;
    }
}

 

PriorityQueue와 Comparator를 활용한 정답코드2입니다.

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        HashMap<Integer, Integer> hashmap = new HashMap<>();
        for(int i=0; i<nums.length; i++){
            hashmap.put(nums[i], hashmap.getOrDefault(nums[i], 0) + 1);
        }

        PriorityQueue<Integer> pq = new PriorityQueue<>(new Comparator<Integer>(){
            @Override
            public int compare(Integer a, Integer b){
                return Integer.compare(hashmap.get(b), hashmap.get(a));
            }
        });

        for(Map.Entry<Integer, Integer> entrySet : hashmap.entrySet()){
            pq.offer(entrySet.getKey());
        }

        int[] answer = new int[k];
        int idx = 0;
        for(int i=0; i<k; i++){
            answer[idx++] = pq.poll();
        }

        return answer;
    }
}