湛江建站公司模板,网站开发的客户群体,网站建设公司推荐万维科技,在网站的主页制作时 填写关键字关注微信公众号#xff1a;怒码少年。 回复关键词#xff1a;【电子书】#xff0c;领取多本计算机相关电子书 大家好#xff0c;我是怒码少年小码。
今天开始进入新的篇章——堆#xff01;这里我默认了大家都知道堆的基本知识了#xff0c;我们来看看关于堆的两道高频… 关注微信公众号怒码少年。 回复关键词【电子书】领取多本计算机相关电子书 大家好我是怒码少年小码。
今天开始进入新的篇章——堆这里我默认了大家都知道堆的基本知识了我们来看看关于堆的两道高频算法题吧。
数组中的第K个最大元素
LeetCode 215给定整数数组 nums 和整数 k请返回数组中第 k 个最大的元素。 示例: 输入: [3,2,1,5,6,4], k 2输出: 5 分析本题的方法有三种选择法、快速排序和堆查找
选择法
类似于冒泡排序第一个排序找出第1大的元素第二次排序找出第2大的元素第k次排序找出第k大的元素。
快速排序之前已经讲过堆查找
利用堆解决这个问题首先思考用最大堆还是最小堆答最小堆。
原因构造一个k大小的最小堆则这个堆里存放的就是前k大的元素只有比堆顶这个堆中最小的元素大才能进入堆中。最后这个堆顶就是第k大的元素。
记忆口诀 查找找大用小大的进找小用大小的进排序升序用小降序用大。 以[323124515623]k4。为例。注意只有当前遍历的元素大于堆顶元素才会入堆否则丢弃。 堆的代码纯手写会很复杂在Java中可以使用优先队列实现。 在 Java 中PriorityQueue 是一个实现了优先队列Priority Queue的类。是基于优先级的队列元素按照一定的优先级顺序进行排序并存储。 public int findKthLargest(int[] nums, int k) {//利用优先队列和最小堆完成if(k nums.length){return -1;}int len nums.length;//创建一个还有k个元素大小的最小堆PriorityQueueInteger minHeap new PriorityQueue(k,(a,b)-a-b);for(int i 0 ; ik ; i){minHeap.add(nums[i]);}for(int i k ; i len ; i){//获取但是不拿出因为还不确定是不是要换Integer topEle minHeap.peek();//只要当前遍历的元素比堆顶元素大堆顶弹出当前遍历的放进去if(nums[i] topEle){minHeap.poll();minHeap.offer(nums[i]);}}return minHeap.peek();
}offer()方法的作用是将元素插入到优先队列中并根据定义的优先级顺序进行排序以便在后续的操作中能够按照优先级顺序提取元素。
合并 K 个升序链表
LeetCode 23给你一个链表数组每个链表都已经按升序排列。请你将所有链表合并到一个升序链表中返回合并后的链表。 示例 输入lists [[1,4,5],[1,3,4],[2,6]]输出[1,1,2,3,4,4,5,6]解释链表数组如下 [ 1-4-5, 1-3-4, 2-6 ] 将它们合并到一个有序链表中得到。 1-1-2-3-4-4-5-6 分析每个队列都是从小到大排序的每次都要找最小的元素我们要用小顶堆不同的是每次比较谁更小
堆合并的策略不管几个链表最终都是按照顺序来的。每次都将剩余节点的最小值加到输出链表尾部然后进行堆调整最后堆空的时候合并完成。
public ListNode mergeKLists(ListNode[] lists) {if(lists null || lists.length 0) return null;
//创建优先队列PriorityQueueListNode q new PriorityQueue(Comparator.comparing(node - node.val));for(int i 0;ilists.length;i){if(lists[i] ! null){q.add(lists[i]);}}ListNode dummy new ListNode(0);ListNode tail dummy;while(!q.isEmpty()){tail.next q.poll();tail tail.next;if(tail.next ! null){q.add(tail.next);}}return dummy.next;
}PriorityQueueListNode q new PriorityQueue(Comparator.comparing(node - node.val)) 这段代码的意思是创建了一个优先队列 q并指定了节点的比较方式。
首先使node - node.val 是一个 Lambda 表达式用于定义优先队列 q 的比较器。它表示一个匿名函数接受 ListNode 类型的参数 node并返回 node.val。
具体来说node - node.val 表达式的作用是根据链表节点的值 val 进行比较。当两个链表节点进行比较时比较器会调用这个表达式来获取节点的值并根据节点值的大小来决定它们的顺序。
通过 Comparator.comparing() 方法我们可以将这个 Lambda 表达式作为比较器传递给 PriorityQueue 构造函数以创建一个根据节点值排序的优先队列。也就是说优先队列 q 中的节点会根据节点值的大小进行排序使得队列中的节点始终以升序排列。
通过循环遍历 lists 数组对每个链表进行判断。如果当前链表不为空即非空链表就将该链表的头节点即最小值节点加入到优先队列 q 中。
进入循环持续执行以下步骤直到优先队列 q 为空
从优先队列 q 中取出当前最小的节点并将其设为 tail 的下一个节点。 将 tail 指向新的节点。如果 tail.next 不为空说明当前的已合并链表还有剩余节点。返回新链表 dummy 的下一个节点即合并后的有序链表的头节点。
