Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.
1 <= nums.length <= 10^5, -10^4 <= nums[i] <= 10^4, k is in the range [1, the number of unique elements]
Count frequencies with hash map, then use bucket sort (index = frequency) or heap to find top k elements in O(n) time.
def topKFrequent(nums, k):
count = Counter(nums)
bucket = [[] for _ in range(len(nums) + 1)]
for num, freq in count.items():
bucket[freq].append(num)
result = []
for i in range(len(bucket) - 1, 0, -1):
for num in bucket[i]:
result.append(num)
if len(result) == k:
return result
return result