Top K Frequent Elements
MediumArrays & Hashing
Given an integer array nums and an integer k, return the k distinct values that occur most often in nums.
The input is guaranteed to have a unique answer: the k-th most frequent value is always strictly more frequent than every value left out, so there are no ties at the cutoff. Return the values in any order.
Follow-up: aim for better than O(n log n) time, where n is the length of nums.
Example 1
- Input:
- nums = [4,4,4,6,6,2], k = 2
- Output:
- [4,6]
- Explanation
- 4 appears three times and 6 twice, the two highest counts. 2 appears once and is left out.
[6,4]would be accepted too.
Example 2
- Input:
- nums = [-5,3,3,-5,8,-5,3,3], k = 1
- Output:
- [3]
- Explanation
- 3 appears four times, -5 three times and 8 once, so 3 alone is the most frequent value.
Example 3
- Input:
- nums = [5,6,5,7], k = 3
- Output:
- [5,6,7]
- Explanation
- There are exactly three distinct values and
kis 3, so all of them are returned.
Constraints
1 <= nums.length <= 10^5-10^4 <= nums[i] <= 10^41 <= k <=number of distinct values innums- The answer is unique (no frequency tie at the
k-th position)