This approach uses a hash map to count the frequency of each element. We then use a min-heap to keep track of the top k elements.
Time Complexity: O(n log n) due to sorting.
Space Complexity: O(n) for storing frequencies.
1from collections import Counter
2import heapq
3
4def topKFrequent(nums, k):
5 count = Counter(nums)
6 return heapq.nlargest(k, count.keys(), key=count.get)
7
8if __name__ == '__main__':
9 nums = [1,1,1,2,2,3]
10 k = 2
11 print(topKFrequent(nums, k))
12We use Python's collections.Counter and heapq.nlargest functions to efficiently get the top k frequent elements.
This approach involves using bucket sort where we create buckets for frequency counts and then extract the top k frequent elements.
Time Complexity: O(n + k).
Space Complexity: O(n).
1function topKFrequent(nums, k) {
2 const freqMap = {};
3 nums.forEach(num => {
4 freqMap[num] = (freqMap[num] || 0) + 1;
5 });
6
7 const buckets = Array(nums.length + 1).fill().map(() => []);
8 Object.keys(freqMap).forEach(num => {
9 buckets[freqMap[num]].push(parseInt(num));
10 });
11
12 const result = [];
13 for (let i = buckets.length - 1; i >= 0 && result.length < k; i--) {
14 if (buckets[i].length > 0) {
15 result.push(...buckets[i]);
16 }
17 }
18 return result.slice(0, k);
19}
20
21const nums = [1, 1, 1, 2, 2, 3];
22const k = 2;
23console.log(topKFrequent(nums, k));
24In JavaScript, elements are counted via a map and ordered into buckets representing frequencies, making it possible to fetch the most frequent.