8ms beats 100%


  • 0
    I

    This is a variation of the formal approach that first maps num to frequency, then throw the nums into priority queue.

    This variation is for fun purpose. It takes advantage that current test cases all have pretty small (max-min), which makes new int[max-min] and scan the array much more lightweight compares to leveraging a hash map.

    public class Solution {
        public List<Integer> topKFrequent(int[] nums, int k) {
            int max = Integer.MIN_VALUE, min = Integer.MAX_VALUE;
            for(final int num : nums) {
                max = Math.max(num, max);
                min = Math.min(num, min);
            }
            
            final int[] paper = new int[max - min + 1];
    
            for(final int num : nums) {
                paper[num - min]++;
            }
            
            final int finalMin = min;
            final PriorityQueue<Integer> pq = new PriorityQueue<>(k, new Comparator<Integer>() {
                public int compare(final Integer num1, final Integer num2) {
                    return paper[num1 - finalMin] - paper[num2 - finalMin];
                }
            });
            
            for(int i=0; i<paper.length; i++) {
                if(paper[i] == 0) continue;
                
                if(pq.size() < k) {
                    pq.offer(i + min);
                    continue;
                }
    
                if(paper[i] <= paper[pq.peek() - min]) {
                    continue;
                }
    
                pq.poll();
                pq.offer(i + min);
            }
            
            final LinkedList<Integer> ans = new LinkedList<>();
    
            while(ans.size() < k && !pq.isEmpty()) {
                ans.addFirst(pq.poll());
            }
            
            return ans;
        }
    }
    

Log in to reply
 

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