前K个高频元素
给定一个非空的整数数组,返回其中出现频率前 k 高的元素。
示例 1:
输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]
示例 2:
输入: nums = [1], k = 1
输出: [1]
思路
在面试中遇到了
自己思路是O(n),遍历得到频率然后再遍历选出前K个
官方,统计频率,堆排序(根据比较器)
解答
class Solution {
public int[] topKFrequent(int[] nums, int k) {
HashMap<Integer, Integer> map = new HashMap<>();
for (int num : nums)
map.put(num, map.getOrDefault(num, 0) + 1);
PriorityQueue<Integer> queue = new PriorityQueue<>((n1, n2) -> map.get(n1) - map.get(n2));
for (int num : map.keySet()) {
queue.offer(num);
if (queue.size() > k) queue.poll();
}
int[] result = new int[k];
for (int i = k - 1; i >= 0; i--)
result[i] = queue.poll();
return result;
}
}