Given a list of integers, return the top k most frequent values.
Example
I: [1, 1, 1, 2, 2, 3], k = 2
O: [1, 2]
I: [3, 2, 1], k = 1
O: the answer is not unique
Simple Heap
def topKFrequent(self, nums: List[int], k: int) -> List[int]:
# use a hash map to reduce this problem to a common top k problem
if len(nums) == 0 or k == 0:
return []
num_dict: Dict[int, int] = {}
for num in nums:
if num in num_dict:
num_dict[num] = num_dict[num] + 1
else:
num_dict[num] = 1
# use a min heap of k elements
min_heap = []
for key in num_dict:
if len(min_heap) < k:
heapq.heappush(min_heap, (num_dict[key], key))
elif num_dict[key] > min_heap[0][0]:
heapq.heappop(min_heap)
heapq.heappush(min_heap, (num_dict[key], key))
return [k for (v, k) in min_heap]
