🎨Now live: Try our Free AI Image Generation Feature

Description
The topKFrequent
function returns the k
most frequent elements from a given list of integers.
Intuition
To determine the k
most frequent elements, we need to first count the occurrences of each element. Once we have the frequencies, we can sort the elements based on their frequencies and select the top k
.
Approach
- Count Frequencies: Use a hash map to count the occurrences of each element in the list.
- Sort by Frequency: Convert the frequency map to a list of pairs and sort it based on the frequency in descending order.
- Extract Top K: Extract the top
k
elements from the sorted list.
Complexity
Time Complexity:
O(n log n), where n
is the number of elements in the input list. This is due to sorting the frequency list.
Space Complexity:
O(n) for storing the frequency map and the result list.
Code
C++
class Solution {
public:
std::vector topKFrequent(std::vector& nums, int k) {
std::unordered_map countMap;
for (const int& num : nums) {
countMap[num]++;
}
std::vector> freqVec(countMap.begin(), countMap.end());
std::sort(freqVec.begin(), freqVec.end(), [](const std::pair& a, const std::pair& b) {
return a.second > b.second;
});
std::vector result;
for (int i = 0; i < k; ++i) {
result.push_back(freqVec[i].first);
}
return result;
}
};
Python
class Solution:
def topKFrequent(self, nums: List[int], k: int) -> List[int]:
count = Counter(nums)
# Sort by frequency and get the top k elements
return [item for item, freq in count.most_common(k)]
Java
class Solution {
public int[] topKFrequent(int[] nums, int k) {
// Create a frequency map
Map countMap = new HashMap<>();
for (int num : nums) {
countMap.put(num, countMap.getOrDefault(num, 0) + 1);
}
PriorityQueue> maxHeap =
new PriorityQueue<>((a, b) -> b.getValue() - a.getValue());
// Add all entries to the max heap
maxHeap.addAll(countMap.entrySet());
// Extract the top k frequent elements
int[] result = new int[k];
for (int i = 0; i < k; i++) {
result[i] = maxHeap.poll().getKey();
}
return result;
}
}
JavaScript
var topKFrequent = function (nums, k) {
// return k most freq elements
const maxCount = 0;
// create map of freq
const map = {};
const freqs = [];
for (const num of nums) {
map[num] = (map[num] || 0) + 1
}
for (const key in map) {
freqs.push([key, map[key]]);
}
const result = freqs.sort((a, b) => b[1] - a[1]).map(arr => parseInt(arr[0]));
return result.slice(0, k);
};