做海报找素材网站,不错的网站建设公司,wordpress跳转到老域名,信主网站概念
队列是一种先进先出(FIFO)的数据结构#xff0c;但有些情况下#xff0c;操作的数据可能带有优先级#xff0c;一般出队列时#xff0c;可能需要优先级高的元素先出队列数据结构应该提供两个最基本的操作#xff0c;一个是返回最高优先级对象#xff0c;一个是添加…概念
队列是一种先进先出(FIFO)的数据结构但有些情况下操作的数据可能带有优先级一般出队列时可能需要优先级高的元素先出队列数据结构应该提供两个最基本的操作一个是返回最高优先级对象一个是添加新的对象。这种数据结构就是优先级队列(Priority Queue) Java集合框架中提供了PriorityQueue和PriorityBlockingQueue两种类型的优先级队列PriorityQueue是线程不安全的PriorityBlockingQueue是线程安全的
注意事项 PriorityQueue中放置的元素应该能够比较大小不能插入无法比较大小的对象 不能插入null插入会抛出NullPointerException异常 new NullPointerException()时默认初始容量为11 插入和删除元素的时间复杂度为 PriorityQueue底层使用了堆数据结构 PriorityQueue默认情况下是小堆---即每次获取到的元素都是最小的元素
常用方法 方法 描述 boolean offer(E e) 入队列 E poll() 出队列 E peek() 得到队首元素 int size() 返回集合中的元素个数 如何使 PriorityQueue 的底层是一个大根堆
下图为 PriorityQueue 的构造方法第一个参数代表数组的大小而第二个参数就一个比较器传给他的就是比较的方法通过给他传入大根堆的比较方式通过传入比较器改变PriorityQueue 成为一个大根堆 案例 三种解法
第一种顺序合并 用一个变量 \ans 来维护以及合并的链表第 i 次循环把第 i 个链表和ans 合并答案保存到 ans 中
第二种分治合并 将 kk 个链表配对并将同一对中的链表合并 第一轮合并以后 k 个链表被合并成了个链表平均长度为,然后是个链表,个链表等等 重复这一过程直到我们得到了最终的有序链表。 第三种使用优先队列合并 我们需要维护当前每个链表没有被合并的元素的最前面一个kk 个链表就最多有 kk 个满足这样条件的元素每次在这些元素里面选取 \textit{val}val 属性最小的元素合并到答案中。在选取最小元素的时候我们可以用优先队列来优化这个过程。
/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val val; }* ListNode(int val, ListNode next) { this.val val; this.next next; }* }*/
class Solution {public ListNode mergeKLists(ListNode[] lists) {PriorityQueueListNode pq new PriorityQueue(new ComparatorListNode() {Overridepublic int compare(ListNode o1, ListNode o2) {return o1.val - o2.val;}}
);ListNode dummy new ListNode(0), cur dummy;for (ListNode list : lists) {if (list ! null) {pq.offer(list);}}while (pq.size() 0) {ListNode node pq.poll();cur.next node;cur cur.next;if (node.next ! null) {pq.offer(node.next);}}return dummy.next;}
} 时间复杂度考虑优先队列中的元素不超过 k 个那么插入和删除的时间代价为 O(logk)这里最多有 kn 个点对于每个点都被插入删除各一次故总的时间代价即渐进时间复杂度为 O(kn×logk)。 空间复杂度这里用了优先队列优先队列中的元素不超过 k 个故渐进空间复杂度为O(k)。
