嘉善公司网站建设联系人青岛网站建设
优先队列
优先队列(priority queue)是计算机科学中的一类抽象数据类型。优先队列中的每个元素都有各自的优先级,优先级最高的元素最先得到服务;优先级相同的元素按照其在优先队列中的顺序得到服务。优先队列通常使用“堆”(heap)实现。
优先队列至少需要支持下述操作:
插入带优先级的元素(insert_with_priority)
取出具有最高优先级的元素(pull_highest_priority_element)
查看最高优先级的元素(peek):O(1) 时间复杂度
其它可选的操作:
检查优先级高的一批元素
清空优先队列
批插入一批元素
合并多个优先队列
调整一个元素的优先级
怎样理解优先队列?
举个例子。一家诊所,只有一个医生为病人看病。每个病人依据他们的病情,都会有一个看病的优先级。抽象出一个队列,当病人进入队列时,代表需要等待医生空闲;出队列时,病人接受治疗。一个病人患了感冒,优先级较低,让他在队列中等待,待医生空闲时再为他治疗;接下来,另一位病人前来看病,这位病人伤得不轻,病人头上插着斧头正血流不止,优先级较高,会让他先出队列进行治疗。
在java中的优先队列是一个最小堆,我们可以通过comparator将其变成最大堆
例题
Top K Frequent Elements
Given 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 = 2
Output: [1,2]
Example 2:
Input: nums = [1], k = 1
Output: [1]
Constraints:
1 <= nums.length <= 105
-104 <= nums[i] <= 104
k is 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.
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/top-k-frequent-elements
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
class Solution {public int[] topKFrequent(int[] nums, int k) {//key:num value:frequencyHashMap<Integer,Integer> map = new HashMap<>();//int[0]:num int[1]:frequencyPriorityQueue<int[]> pq = new PriorityQueue<>(new Comparator<int[]>() {@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.Entry<Integer, 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;}
}