K Most Frequent Numbers

MediumHash mapHeapSorting203 tests

You get an integer array nums and an integer k.

Find the k numbers that appear most often in nums. Return them as an array, in this order:

A number that appears more times comes first.
If two numbers appear the same number of times, the smaller number comes first.

Each number appears in the result at most once. k is never larger than the count of different numbers in nums.

Hint

First count how many times each number appears, with a hash map. Then you need the best k entries by the rule above. You can sort all entries, or keep a heap of size k, which takes O(n log k) time.

Examples

Example 1

Input:: [5,3,5,8,3,5,1], 2
Output:: [5,3]

5 appears 3 times and 3 appears 2 times. 8 and 1 appear once each, so they are not in the top 2.

Example 2

Input:: [4,-2,9,-2,4,9], 2
Output:: [-2,4]

-2, 4 and 9 each appear 2 times. With equal counts the smaller numbers come first, so the answer is -2 then 4.

Example 3

Input:: [10], 1
Output:: [10]

There is only one number, so it is the answer.

Constraints

1 <= nums.length <= 50
-30 <= nums[i] <= 30
1 <= k <= the number of different values in nums

Run checks your code against the 3 examples. Submit checks it against all 203 tests and needs a free account. You can also try ideas in the free JavaScript or Python compiler.