You are given a list of integers nums and an integer k. Return the k values that appear
most often in nums, in any order.
The tests are chosen so the answer is unique: each of the k values appears strictly more often
than every value left out.
Example 1
- Input
- nums = [5, 3, 5, 9, 3, 5], k = 2
- Output
- [5, 3]
5 appears three times and 3 twice; 9 appears only once.Example 2
- Input
- nums = [-1, -1, 4], k = 1
- Output
- [-1]
Constraints
numsholds 1 to 10⁵ numbers, each between −10⁴ and 10⁴.kis between 1 and the number of different values innums.- There is no tie at the boundary, so exactly one set of
kvalues is right.
Show the pattern
Hashing, Heap
First you need how often each value appears, which is a counting hash map. Then you need only the k largest counts, which a heap (or buckets indexed by count) gives without sorting everything.
See hashing in a visualiserShow the approach
Count each value with a hash map. Then make buckets: buckets[c] lists the values that appear
exactly c times, where c is at most n. Walk the buckets from n down to 1, collecting
values, and stop as soon as you have k. Because the answer is unique, you never have to choose
between values with the same count at the boundary.
A min-heap of size k keyed by count also works, in O(n log k): push each value, and pop the
least frequent whenever the heap holds more than k.
Time: O(n) · Space: O(n)