The k most common values
Find the k values that occur most often, by counting each value and keeping a small heap of the most frequent counts. About 16 minutes.
Count first
You cannot find the most common values without knowing how often each value occurs. So first make a pass over the array, counting each value in a map from value to count.
Now the question is about the map: which k entries have the biggest counts? That is the same top-k pattern as before, but the thing being compared is the count.
count = {}
for x in nums:
count[x] = count.get(x, 0) + 1Counting finishes: 1 appears 3 times, 2 appears twice, 3 appears once.
A key that breaks ties
Keep a min-heap of size k, so that the least common of the kept values is on top and is the first to be removed. Each heap entry is a pair: the count, and then something that settles ties.
If two values have the same count, the task prefers the smaller value. So the entry that should be removed first, the worse one, has the larger value. Storing the negated value as the second part of the pair does exactly that. Finally sort the survivors by count, biggest first, and then by value.
heapq.heappush(heap, (c, -value))
if len(heap) > k:
heapq.heappop(heap)Two values both appear 4 times and only one can be kept. Which one does the task keep?
- AThe smaller value
- BThe larger value
- CEither one
Show the answer
The smaller value. Ties in count are settled in favour of the smaller value.
Top k frequent elements
Given an integer array nums and an integer k, return the k most frequent values, listed from the most frequent to the least frequent. If two values have the same frequency, the smaller value comes first. It is guaranteed that k does not exceed the number of distinct values.
nums = [1, 1, 1, 2, 2, 3], k = 2 → [1, 2]
1 ≤ length of nums ≤ 100,000 · -10,000 ≤ nums[i] ≤ 10,000 · 1 ≤ k ≤ number of distinct values