Dare2Solve
The topKFrequent
function returns the k
most frequent elements from a given list of integers.
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
.
k
elements from the sorted list.O(n log n), where n
is the number of elements in the input list. This is due to sorting the frequency list.
O(n) for storing the frequency map and the result list.
class Solution {
public:
std::vector<int> topKFrequent(std::vector<int>& nums, int k) {
std::unordered_map<int, int> countMap;
for (const int& num : nums) {
countMap[num]++;
}
std::vector<std::pair<int, int>> freqVec(countMap.begin(), countMap.end());
std::sort(freqVec.begin(), freqVec.end(), [](const std::pair<int, int>& a, const std::pair<int, int>& b) {
return a.second > b.second;
});
std::vector<int> result;
for (int i = 0; i < k; ++i) {
result.push_back(freqVec[i].first);
}
return result;
}
};
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)]
class Solution {
public int[] topKFrequent(int[] nums, int k) {
// Create a frequency map
Map<Integer, Integer> countMap = new HashMap<>();
for (int num : nums) {
countMap.put(num, countMap.getOrDefault(num, 0) + 1);
}
PriorityQueue<Map.Entry<Integer, Integer>> 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;
}
}
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);
};