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()) {
queue.add(key);
}
int preCount = 0;
for (int i = 0; i < k; i++) {
int num = queue.poll();
ans.add(num);
preCount = countMap.get(num);
}
// These elements of same count must be included.
while (!queue.isEmpty() && preCount == countMap.get(queue.peek())) {
ans.add(queue.poll());
}
return ans;
}
}