Problem
Given an integer array nums and an integer k, return the k most frequent elements. The result may be returned in any order.Example(s)
Consider the following example(s) to understand the expected input and output.Input
nums = [1,1,1,2,2,3]
k = 2 Output
[1,2] Solution
This solution first uses a HashMap to count the frequency of each number.A Min Heap is then used to keep track of the k most frequent elements. Each unique number is added to the heap along with its frequency. If the heap size becomes greater than k, the element with the lowest frequency is removed.
After processing all unique elements, the heap contains the k most frequent elements, which are then added to the result.
public int[] topKFrequent(int[] nums, int k) {
Map<Integer, Integer> frequency = new HashMap<>();
// Count the frequency of each number.
for (int num : nums) {
frequency.put(num, frequency.getOrDefault(num, 0) + 1);
}
PriorityQueue<Integer> minHeap = new PriorityQueue<>(
(a, b) -> frequency.get(a) - frequency.get(b)
);
for (int num : frequency.keySet()) {
minHeap.offer(num);
// Keep only the k most frequent elements.
if (minHeap.size() > k) {
minHeap.poll();
}
}
int[] result = new int[k];
for (int i = k - 1; i >= 0; i--) {
result[i] = minHeap.poll();
}
return result;
}
Complexity
Building the frequency map takesO(n) time. Each of the m unique elements is inserted into the heap, and each heap operation takes O(log k) time, resulting in an overall time complexity of O(n + m log k). 