# 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](https://leetcode.com/subscribe/) to see which companies asked this question.

Hide Tags

[Hash Table](https://leetcode.com/tag/hash-table/) [Heap](https://leetcode.com/tag/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;

    }
```