Leetcode
Youtube
Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.
Test Cases
Example 1:
Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]
Example 2:
Input: nums = [1], k = 1
Output: [1]
Constraints:
1 <= nums.length <= 10<sup>5</sup>-10<sup>4</sup> <= nums[i] <= 10<sup>4</sup>kis in the range[1, the number of unique elements in the array].- It is guaranteed that the answer is unique.
Follow up: Your algorithm’s time complexity must be better than
O(n log n), where n is the array’s size.
Solution
class Solution {
public int[] topKFrequent(int[] nums, int k) {
Map<Integer, Integer> count = new HashMap<>();
PriorityQueue<Integer> pq = new PriorityQueue((a, b) -> count.getOrDefault(b,0) - count.getOrDefault(a, 0));
for(int n: nums) {
if (!count.containsKey(n)) {
pq.offer(n);
}
count.put(n, count.getOrDefault(n, 0) + 1);
}
int[] result = new int[k];
int i = 0;
while(!pq.isEmpty() && i<k) {
result[i++] = pq.poll();
}
return result;
}
}