Top K Frequent Elements

PriorityQueue<Map.Entry<Integer, Integer>> heap = new PriorityQueue<>((a,b) -> (a.getValue() - b.getValue()));

java 定制排序 Comparator 区分从大到小还是从小到大_comparator从大到小排序-CSDN博客blog.csdn.net

Given a non-empty array of integers, return the k most frequent elements.

Example 1:

Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]

Example 2:

Input: nums = [1], k = 1
Output: [1]

Note:

• You may assume k is always valid, 1 ≤ k ≤ number of unique elements.

• Your algorithm's time complexity must be better than O(n log n), where n is the array's size.

n+n*logk

priority queue based on heap, o(logn) most time, here totally time o(n)

class Solution {
    public List<Integer> topKFrequent(int[] nums, int k) {
        List<Integer> res = new ArrayList<>();
        
        
        if(nums == null || nums.length == 0){
            return res;
        }
        
        Map<Integer,Integer> map = new HashMap<>();
        
        for(int i = 0; i <nums.length;i++){
            if(!map.containsKey(nums[i])){
                map.put(nums[i],1);
            }else{
                map.put(nums[i],map.get(nums[i])+1);
            }
        }
        
        //从小到大排序
        PriorityQueue<Map.Entry<Integer,Integer>> queue = new PriorityQueue<Map.Entry<Integer,Integer>>(
            new Comparator<Map.Entry<Integer,Integer>>(){
                public int compare(Map.Entry<Integer,Integer> e1,Map.Entry<Integer,Integer> e2){
                    return e1.getValue() - e2.getValue();
                }
            }
        );
        
        
        for(Map.Entry<Integer,Integer> entry : map.entrySet()){
            if(queue.size() < k){
                queue.offer(entry);
            }else{
                if(queue.peek().getValue() < entry.getValue()){
                    queue.poll();
                    queue.offer(entry);
                }
            }
        }
        
        for(Map.Entry<Integer,Integer> entry:queue){
            res.add(entry.getKey());
        }
        
        return res;
        
    }
}

二刷

class Solution {
    public List<Integer> topKFrequent(int[] nums, int k) {
        List<Integer> res = new ArrayList<>();
        
        if(nums == null || nums.length == 0)
            return res;
        
        
        Map<Integer,Integer> map = new HashMap<>();
        
        for(int x : nums){
            map.put(x,map.getOrDefault(x,0)+1);
        }
        
        
        PriorityQueue<Map.Entry<Integer,Integer>> queue = PriorityQueue<>(
            new Comparator<Map.Entry<Integer,Integer>>(){
                public int compare(Map.Entry<Integer,Integer> e1, Map.Entry<Integer,Integer> e2){
                    return e1.getValue() - e2.getValue();
                }
            }
        );
        
        
        //better than n logn ,不是每一个都要插入queue
        for(Map.Entry<Integer,Integer> e : map.entrySet()){
            if(queue.size() < k){
                queue.offer(e);
            }else{
                if(queue.peek.getValue() < e.getValue){
                    queue.pop();
                    queue.offer(e);
                }
            }
        }
        
        
        for(Map.Entry<Integer,Integer> e: queue){
            res.add(e.getKey());
        }
        
        return res;
    }
}

三刷

class Solution {
    public List<Integer> topKFrequent(int[] nums, int k) {
        List<Integer> res = new ArrayList<>();
        
        if(nums == null || nums.length == 0)
            return res;
        
        
        Map<Integer,Integer> map = new HashMap<>();
        
        for(int x : nums){
            map.put(x,map.getOrDefault(x,0)+1);
        }
        
        
        // PriorityQueue<Map.Entry<Integer,Integer>> queue = new PriorityQueue<>(
        //     new Comparator<Map.Entry<Integer,Integer>>(){
        //         public int compare(Map.Entry<Integer,Integer> e1, Map.Entry<Integer,Integer> e2){
        //             return e1.getValue() - e2.getValue();
        //         }
        //     }
        // );
        
        PriorityQueue<Map.Entry<Integer,Integer>> queue = new PriorityQueue<>((e1,e2) -> e1.getValue() - e2.getValue());
        
        // PriorityQueue<Map.Entry<Integer, Integer>> queue = new PriorityQueue<Map.Entry<Integer, Integer>>(
        //     new Comparator<Map.Entry<Integer, Integer>>() {
        //         public int compare(Map.Entry<Integer, Integer> e1, Map.Entry<Integer, Integer> e2) {
        //             return e1.getValue() - e2.getValue();
        //         }
        //     });
        //better than n logn ,不是每一个都要插入queue
        for(Map.Entry<Integer,Integer> e : map.entrySet()){
            if(queue.size() < k){
                queue.offer(e);
            }else{
                if(queue.peek().getValue() < e.getValue()){
                    queue.poll();
                    queue.offer(e);
                }
            }
        }
        
        
        for(Map.Entry<Integer,Integer> e: queue){
            res.add(e.getKey());
        }
        
        return res;
    }
}