347.Top K Frequent Elements

1.Description(Medium)

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

For example, Given[1,1,1,2,2,3]and k = 2, return[1,2].

Note:

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

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

Subscribe to see which companies asked this question.

Hide Tags

Hash Table Heap

2.Code

这个题跟top k frequent words很像，区别是那道题是arrays of strings, 本题是arrays of int.

用一个hashmap和一个PriorityQueue<Map.Entry<Integer,Integer>> 来解决。

word那道题用了一个class 来封装string 和frequency,本题直接用map.entry来解决了。

public List<Integer> topKFrequent(int[] nums, int k) {
        List<Integer> result=new ArrayList<Integer>();
        HashMap<Integer,Integer> map=new HashMap<Integer,Integer>();
        if(nums==null || nums.length==0 || k<1){
            return result;
        }
        for(int i=0;i<nums.length;i++){
            if(map.containsKey(nums[i])){
                map.put(nums[i],map.get(nums[i])+1);
            }else{
                map.put(nums[i],1);
            }
        }
        PriorityQueue<Map.Entry<Integer,Integer>> queue=new PriorityQueue<Map.Entry<Integer,Integer>>(k,
            new Comparator<Map.Entry<Integer,Integer>>(){
            public int compare(Map.Entry<Integer,Integer> a,Map.Entry<Integer,Integer> b){
                return a.getValue()-b.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){
            result.add(entry.getKey());
        }
        return result;

    }