Description
Return the k most frequent values. The answer set is unique and its order does not matter.
Solution
from collections import Counter
def top_k_frequent(nums, k):
counts = Counter(nums)
buckets = [[] for _ in range(len(nums) + 1)]
for value, frequency in counts.items():
buckets[frequency].append(value)
result = []
for bucket in reversed(buckets):
for value in bucket:
result.append(value)
if len(result) == k:
return resultExamples
Inputs are positional arguments. Trees use level-order arrays; linked lists use value arrays. Design problems list operations in order.
Example 1
- Input
[[7,7,7,2,2,9],2]- Output
[7,2]
7 occurs three times and 2 twice.
Example 2
- Input
[[5],1]- Output
[5]
5 is the only value.
Example 3
- Input
[[-1,-1,0],1]- Output
[-1]
-1 appears more often than 0.
Approach
Count each value, then bucket values by frequency and scan buckets from largest to smallest.
Time & space
O(n) expected time; O(n) space, for n entries.