Top K Frequent Elements
- 1 min read
- Array
- LC-Medium
3 years ago
Solution
- Since a number cannot occur more than n times in the array, use a variant of Bucket Sort
- Each element's frequency minus one is the index in the buckets array. Each element in this buckets array is a list which you will append numbers to that have the count same as the index.
- Do this until you have k numbers in the buckets array
| Time | Space | Explanation |
|---|---|---|
O(n) | O(1) |
def topKFrequent(self, nums: List[int], k: int) -> List[int]:
counts = Counter(nums)
buckets = [[] for i in range(len(nums))]
for num, count in counts.items():
buckets[count - 1].append(num)
ans = []
for i in range(len(buckets) - 1, -1, -1):
for num in buckets[i]:
ans.append(num)
k -= 1
if k == 0:
return ans