作者:whisper
链接:https://www.proprogrammar.com/article/887
声明:请尊重原作者的劳动,如需转载请注明出处
对于top k问题,可以使用优先队列(大顶堆,小顶堆)
给定一个非空的整数数组,返回其中出现频率前 k 高的元素。
示例 1:
输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]
示例 2:
输入: nums = [1], k = 1
输出: [1]
JAVA解法
public int[] topKFrequent(int[] nums, int k) {
Map<Integer, Integer> map = new HashMap<>();
for(int n: nums){
map.put(n, map.getOrDefault(n, 0) + 1);
}
PriorityQueue<Long> queue = new PriorityQueue<Long>((l1, l2) -> l2.compareTo(l1));
for(int key: map.keySet()){
queue.offer((map.get(key).longValue() << 32) + key);
}
int[] res = new int[k];
for(int i = 0; i < k; i++){
res[i] = (int)(queue.poll() & 0xffffffff);
}
return res;
}
使用哈希表+优先队列,哈希表存出现次数,优先队列对次数排序,这里有个技巧是把int型的原数和出现次数同时存在一个long型的数中
亲爱的读者:有时间可以点赞评论一下
全部评论