---
# System prepended metadata

title: 347. Top K Frequent Elements
tags: [leetcode, medium, heapsort]

---


# 347. Top K Frequent Elements

###### tags: `leetcode`,`heapsort`,`medium`



>ref: https://leetcode.com/problems/top-k-frequent-elements/
>
Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.

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

>Example 2:
Input: nums = [1], k = 1
Output: [1]
 

>Constraints:
1 <= nums.length <= 105
k is in the range [1, the number of unique elements in the array].
It is guaranteed that the answer is unique.



>1. poll O(1), foreach loop 似乎比較慢(leetcode測試)
>2. minheap可鎖住priorityQueue 數量為k(超過時先add再poll)

```java=
    public int[] topKFrequent(int[] nums, int k) {
        
        Map<Integer,Integer> r= new HashMap<>();
        
        for(int num:nums){
            r.put(num,r.getOrDefault(num,0)+1);
        }
        
        PriorityQueue<Map.Entry<Integer,Integer>> ans_pre= new PriorityQueue<>((a,b)->a.getValue()-b.getValue());
        
        for(Map.Entry<Integer,Integer> ke: r.entrySet()){
            ans_pre.add(ke);
            if(ans_pre.size()>k){
                ans_pre.poll();
            }
        }
        
        
        int[] res= new int[k];
        int count=0;   
        while(count<k){
            Map.Entry<Integer, Integer> entry = ans_pre.poll();
            res[count++]=entry.getKey();
        }
        
        return res;
    }
```
    
    
    
