南京市城市建设档案馆网站,能发布自做的视频网站,wordpress主题手机端,网站建设及维护专业优先队列优先队列#xff08;priority queue#xff09;是计算机科学中的一类抽象数据类型。优先队列中的每个元素都有各自的优先级#xff0c;优先级最高的元素最先得到服务#xff1b;优先级相同的元素按照其在优先队列中的顺序得到服务。优先队列通常使用“堆”#xf…优先队列优先队列priority queue是计算机科学中的一类抽象数据类型。优先队列中的每个元素都有各自的优先级优先级最高的元素最先得到服务优先级相同的元素按照其在优先队列中的顺序得到服务。优先队列通常使用“堆”heap实现。优先队列至少需要支持下述操作插入带优先级的元素insert_with_priority取出具有最高优先级的元素pull_highest_priority_element查看最高优先级的元素peekO(1) 时间复杂度其它可选的操作检查优先级高的一批元素清空优先队列批插入一批元素合并多个优先队列调整一个元素的优先级怎样理解优先队列举个例子。一家诊所只有一个医生为病人看病。每个病人依据他们的病情都会有一个看病的优先级。抽象出一个队列当病人进入队列时代表需要等待医生空闲出队列时病人接受治疗。一个病人患了感冒优先级较低让他在队列中等待待医生空闲时再为他治疗接下来另一位病人前来看病这位病人伤得不轻病人头上插着斧头正血流不止优先级较高会让他先出队列进行治疗。在java中的优先队列是一个最小堆我们可以通过comparator将其变成最大堆例题Top K Frequent ElementsGiven an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order. Example 1:Input: nums [1,1,1,2,2,3], k 2Output: [1,2]Example 2:Input: nums [1], k 1Output: [1] Constraints:1 nums.length 105-104 nums[i] 104k is in the range [1, the number of unique elements in the array].It is guaranteed that the answer is unique. Follow up: Your algorithms time complexity must be better than O(n log n), where n is the arrays size.来源力扣LeetCode链接https://leetcode.cn/problems/top-k-frequent-elements著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。class Solution {public int[] topKFrequent(int[] nums, int k) {//key:num value:frequencyHashMapInteger,Integer map new HashMap();//int[0]:num int[1]:frequencyPriorityQueueint[] pq new PriorityQueue(new Comparatorint[]() {Overridepublic int compare(int[] o1, int[] o2) {return o2[1] - o1[1];}});//iterate through nums and insert k-v into mapfor(int num : nums) {map.put(num,map.getOrDefault(num,0) 1);}for (Map.EntryInteger, Integer entry : map.entrySet()) {Integer key entry.getKey();Integer value entry.getValue();pq.add(new int[]{key,value});}int[] ans new int[k];for (int i 0;i k;i) {ans[i] pq.poll()[0];}return ans;}
}
