溧阳手机网站设计,临沧市网站建设,设计公司起名字寓意好的字,wordpress 直接连接关卡名 堆能高效解决的经典问题 我会了✔️ 内容 1.掌握数组中寻找第K的元素 ✔️ 2.理解堆排序的原理 ✔️ 3.合并K个排序链表 ✔️
1 在数组中找第K大的元素
LeetCode215 给定整数数组nums和整数k#xff0c;请返回数组中第k个最大的元素。 请注意#xff0c;你需要… 关卡名 堆能高效解决的经典问题 我会了✔️ 内容 1.掌握数组中寻找第K的元素 ✔️ 2.理解堆排序的原理 ✔️ 3.合并K个排序链表 ✔️
1 在数组中找第K大的元素
LeetCode215 给定整数数组nums和整数k请返回数组中第k个最大的元素。 请注意你需要找的是数组排序后的第k个最大的元素而不是第k个不同的元素。 示例1 输入: [3,2,1,5,6,4] 和 k 2 输出: 5 示例2 输入: [3,2,3,1,2,4,5,5,6] 和 k 4 输出: 4 这个题是一道非常重要的题主要解决方法有三个选择法堆查找法和快速排序法。 选择法很简单就是先遍历一遍找到最大的元素然后再遍历一遍找第二大的然后再遍历一遍找第三大的直到第K次就找到了目标值了。但是这种方法只适合在面试的时候预热面试官不会让你这么简单就开始写代码因为该方法的时间复杂度为O(NK)。 比较好的方法是堆排序法和快速排序法。快速排序我们已经分析过这里先看堆排序如何解决问题。 这个题其实用大堆小堆都可以解决的但是我们推荐“找最大用小堆找最小用大堆找中间用两个堆”这样更容易理解适用范围也更广。我们构造一个大小只有4的小根堆为了更好说明情况我们扩展一下序列[3,2,3,1, 2 ,4 ,5, 1,5,6,2,3]。 堆满了之后对于小根堆并一定所有新来的元素都可以入堆的只有大于根元素的才可以插入到堆中否则就直接抛弃。这是一个很重要的前提。 另外元素进入的时候先替换根元素如果发现左右两个子树都小该怎么办呢很显然应该与更小的那个比较这样才能保证根元素一定是当前堆最小的。假如两个子孩子的值一样呢那就随便选一个。 新元素插入的时候只是替换根元素然后重新构造成小堆完成之后你会神奇的发现此时根的根元素正好是第4大的元素。 这时候你会发现不管要处理的序列有多大或者是不是固定的根元素每次都恰好是当前序列下的第K大元素。上面的图收篇幅所限我们省略了部分调整环节请读者自行画一下看看。 上的代码自己实现是非常困难的我们可以使用jdk的优先队列来解决其思路是很简单的。由于找第 K 大元素其实就是整个数组排序以后后半部分最小的那个元素。因此我们可以维护一个有 K 个元素的最小堆
如果当前堆不满直接添加堆满的时候如果新读到的数小于等于堆顶肯定不是我们要找的元素只有新遍历到的数大于堆顶的时候才将堆顶拿出然后放入新读到的数进而让堆自己去调整内部结构。
说明这里最合适的操作其实是 replace()即直接把新读进来的元素放在堆顶然后执行下沉siftDown()操作。Java 当中的 PriorityQueue 没有提供这个操作只好先 poll() 再 offer()。 优先队列的写法就很多了这里只例举一个有代表性的其它的写法大同小异没有本质差别。 import java.util.PriorityQueue;
public class Solution {public int findKthLargest(int[] nums, int k) {if(knums.length){return -1;}int len nums.length;// 使用一个含有 k 个元素的最小堆PriorityQueueInteger minHeap new PriorityQueue(k, (a, b) - a - b);for (int i 0; i k; 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();}
}
堆查找与一般查找方法的优势是可以对超大数量的数据进行查找还能对数量未知的流数据查找例如LeetCode703.本题条件比较啰嗦我们不再赘述感兴趣的同学可以研究一下。 本部分的重点要在理解的基础上记住一个结论找第K大用小根堆找第K小用大根堆。 具体来说 1.K多大就建立多大固定大小的堆 2.找最大用小堆 3.只有比根元素大的才让进入堆。 2 堆排序原理
查找找小用大找大用小 排序升序用小降序用大。 前面介绍了如何用堆来进行特殊情况的查找堆的另一个很重要的作用是可以进行排序那怎么排的呢其实非常简单我们知道在大顶堆中根节点是整个结构最大的元素我先将其拿走剩下的重排此时根节点就是第二大的元素我再将其拿走再排依次类推。最后堆只剩一个元素的时候是不是拿走的数据也就排好序了 具体来说建堆结束之后数组中的数据已经是按照大顶堆的特性来组织的。数组中的第一个元素就是堆顶也就是最大的元素。我们把它跟最后一个元素交换那最大元素就放到了下标为 n 的位置。 这个过程有点类似上面讲的“删除堆顶元素”的操作当堆顶元素移除之后我们把下标为 n 的元素放到堆顶然后再通过堆化的方法将剩下的 n−1 个元素重新构建成堆。堆化完成之后我们再取堆顶的元素放到下标是 n−1 的位置一直重复这个过程直到最后堆中只剩下标为 1 的一个元素排序工作就完成了。 当然在上面的过程中放到最后一个位置的元素就不参与排序和计算了。 看一个例子我们对上面第一章的序列 [12 23 54 2 65 45 92 47 204 31]进行排序首先构建一个大顶堆然后每次我们都让根元素出堆剩下的继续调整为大顶堆 这时候你会发现出堆的序列刚好是204、92、65、54、47、45...。也就是刚好是从大到小的顺序排列的。 所以我们可以明白 如果是一个小顶堆那自然是升序的。所以在排序的时候 排序升序用小降序用大。 这个与前面的查找是相反的。 明白了这几个堆的特征再做相关题目就毫无压力了。
3 合并K个排序链表
Leetcode23.给你一个链表数组每个链表都已经按升序排列。请你将所有链表合并到一个升序链表中返回合并后的链表。 示例1 输入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; i lists.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;
}
