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).
1from collections import Counter
2
3def topKFrequent(nums, k):
4 count = Counter(nums)
5 buckets = [[] for _ in range(len(nums) + 1)]
6
7 for num, freq in count.items():
8 buckets[freq].append(num)
9
10 result = []
11 for i in range(len(buckets) - 1, 0, -1):
12 for num in buckets[i]:
13 result.append(num)
14 if len(result) == k:
15 return result
16
17if __name__ == '__main__':
18 nums = [1, 1, 1, 2, 2, 3]
19 k = 2
20 print(topKFrequent(nums, k))
21Even with Python, we leverage frequency count with buckets to directly access and collect top k frequent elements.