nlogk solution in Java


  • 0
    L
        public List<Integer> topKFrequent(int[] nums, int k) {
            Map<Integer,Integer> map = new HashMap<>();
            //O(n) traversal
            for(int i=0;i<nums.length;i++) {
                map.put(nums[i],map.getOrDefault(nums[i],0)+1);
            }
            //min heap.
            PriorityQueue<Wrapper> queue = new PriorityQueue<>();
            //nlogk
            for(Map.Entry<Integer,Integer> entry : map.entrySet()) {
                queue.add(new Wrapper(entry.getKey(),entry.getValue()));
                if(queue.size()>k) {
                    queue.remove();
                }
            }
            
            LinkedList<Integer> list = new LinkedList<>();
            //klogk
            while(!queue.isEmpty()) {
                list.addFirst(queue.poll().num);
            }
            return list;
            
        }
        private class Wrapper implements Comparable<Wrapper> {
            int num;
            int freq;
            Wrapper(int num,int freq) {
                this.num = num;
                this.freq = freq;
            }
            public int compareTo(Wrapper o) {
                return  this.freq-o.freq;
            }
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.