The K Most Frequent

Write top_k_frequent(nums, k) that returns a list of the k values that appear most often in nums, most frequent first.

When two values appear the same number of times, the smaller value comes first. If the list has fewer than k different values, return all of them in that order.

Examples

top_k_frequent([1, 1, 1, 2, 2, 3], 2)  # returns [1, 2]
top_k_frequent([4, 4, 6, 6, 5], 3)     # returns [4, 6, 5]
top_k_frequent([7, 3, 7, 3, 9, 9], 2)  # returns [3, 7]

In the last example all three values appear twice, so they are ranked by value (3, 7, then 9) and the first two are kept.

Constraints

• 0 <= len(nums) <= 100,000
• 0 <= k <= 100,000
• Values are integers and can be negative