# 347. Top K Frequent Elements (Medium)

https://leetcode.com/problems/top-k-frequent-elements/

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.

## Solutions

``````class Solution {

// Sort the elements by its frequency in given array.

public List<Integer> topKFrequent(int[] nums, int k) {
List<Integer> ans = new ArrayList<>();

if (nums == null || nums.length == 0) {
return ans;
}

// Figure out the count of each unique number
Map<Integer, Integer> countMap = new HashMap<>();
for (int n : nums) {
if (!countMap.containsKey(n)) {
countMap.put(n, 0);
}

countMap.put(n, countMap.get(n) + 1);
}

// The time complexity of sorting operation is O(nlogn)
Queue<Integer> queue = new PriorityQueue<>((o1, o2) -> countMap.get(o2) - countMap.get(o1));

for (Integer key : countMap.keySet()) {
}

int preCount = 0;
for (int i = 0; i < k; i++) {
int num = queue.poll();
preCount = countMap.get(num);
}

// These elements of same count must be included.
while (!queue.isEmpty() && preCount == countMap.get(queue.peek())) {
}

return ans;
}
}
``````