Top K Frequent Elements
Given an integer array nums and an integer k, return the top k frequent elements in the array.
Constraints:
- 1 <= nums.length <= 10^5
- 1 <= k <= 10^5
- It is guaranteed that the answer is unique.
Examples:
Input: [1,1,1,2,2,3] and k = 2
Output: [1,2]
Explanation: The elements 1 and 2 are the top 2 frequent elements in the array.
Solutions
Hash Table and Heap
Time: O(N log k)Space: O(N)
We use a hash table to count the frequency of each element in the array. Then we use a max heap to find the top k frequent elements.
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;
class Solution {
public int[] topKFrequent(int[] nums, int k) {
Map<Integer, Integer> count = new HashMap<>();
for (int num : nums) {
count.put(num, count.getOrDefault(num, 0) + 1);
}
PriorityQueue<Map.Entry<Integer, Integer>> maxHeap = new PriorityQueue<>((a, b) -> b.getValue() - a.getValue());
for (Map.Entry<Integer, Integer> entry : count.entrySet()) {
maxHeap.offer(entry);
}
int[] result = new int[k];
for (int i = 0;
i < k;
i++) {
result[i] = maxHeap.poll().getKey();
}
return result;
}
}Follow-up:
What if the input array is very large and does not fit into memory?
