347. Top K Frequent Elements

문제

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

코드

import java.util.*;

class Solution {

    class Node implements Comparable<Node>{
        int num;
        int count;

        public Node(int num, int count){
            this.num = num;
            this.count = count;
        }

        @Override
        public int compareTo(Node n){
            if(this.count < n.count)
                return 1;
            else if(this.count == n.count)
                return 0;
            return -1;
        }

    }

    public int[] topKFrequent(int[] nums, int k) {
        List<Integer> res = new ArrayList<>();
        Map<Integer, Integer> m = new HashMap<>();
        PriorityQueue<Node> pq = new PriorityQueue<>();

        for(int num : nums){
            if(m.get(num) == null)
                m.put(num, 0);
            m.replace(num, m.get(num)+1);
        }

        for(int key : m.keySet()){
            pq.add(new Node(key, m.get(key)));
        }

        while(k-- != 0){
            res.add(pq.poll().num);
        }

        return res.stream().mapToInt(Integer::intValue).toArray();
    }
}

피드백

• 문제에 시간복잡도 O(nlogn) 안에 풀으라길래 그냥 PriorityQueue(Heap)을 사용해서 풀었음
  • Comparable 인터페이스를 사용해서 구현했다.
• 근데 O(N) 짜리 답안이 있다.
  • https://leetcode.com/problems/top-k-frequent-elements/discuss/81602/Java-O(n)-Solution-Bucket-Sort
  • bucket sort라는 알고리즘을 사용한다 (https://ratsgo.github.io/data%20structure&algorithm/2017/10/18/bucketsort/)
  • leetcode에는 천재들이 많다.