作者: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型的数中
亲爱的读者:有时间可以点赞评论一下
月份 | 原创文章数 |
---|---|
202206 | 4 |
202205 | 2 |
202204 | 1 |
202203 | 11 |
202201 | 2 |
202108 | 7 |
202107 | 3 |
202106 | 16 |
202105 | 10 |
202104 | 16 |
202103 | 56 |
202102 | 14 |
202010 | 3 |
202009 | 3 |
202008 | 7 |
202007 | 7 |
202006 | 10 |
202005 | 11 |
202004 | 22 |
202003 | 52 |
202002 | 44 |
202001 | 83 |
201912 | 52 |
201911 | 29 |
201910 | 41 |
201909 | 99 |
201908 | 35 |
201907 | 73 |
201906 | 121 |
201811 | 1 |
201810 | 2 |
201804 | 1 |
201803 | 1 |
201802 | 1 |
201707 | 1 |
全部评论