做企业网站通常哪找素材,网站分析 案例,京津冀协同发展的先行领域,手机万能浏览器白银挑战-堆能高效解决的经典问题
1.在数组中找第K大的元素
LeetCode215 https://leetcode.cn/problems/kth-largest-element-in-an-array/
思路分析
主要解决方法有3个#xff0c;选择法#xff0c;堆查找法和快速排序法
方法1#xff1a;选择法 先遍历一遍找到最大的…白银挑战-堆能高效解决的经典问题
1.在数组中找第K大的元素
LeetCode215 https://leetcode.cn/problems/kth-largest-element-in-an-array/
思路分析
主要解决方法有3个选择法堆查找法和快速排序法
方法1选择法 先遍历一遍找到最大的元素再遍历一遍找第二大的依次直到第K次就找到了目标值了
方法2堆排序法 用大堆和小堆都可以推荐找最大用小堆找最小用大堆找中间用两个堆
构造一个大小只有k的小根堆 堆满了之后对于小根堆并不一定所有新来的元素都可以入堆的只有大于根元素的才可以插入到堆中否则直接抛弃 完成之后此时根元素恰好时当前序列下第K大的元素
代码实现 代码自己实现起来比较困难可以使用jdk的优先队列来解决
维护一个有k个元素的最小堆如果当前堆不满直接添加堆满的时候如果新读到的数小于堆顶不操作如果大于堆顶将堆顶拿出然后放入新读到的数进而让堆自己调整内部结构
方法3快速排序法 之前已经分析过了见前面内容
代码实现
import java.util.PriorityQueue;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; ik; i){minHeap.add(nums[i]);}for(int ik; ilen; i){// 看一眼不拿出因为有可能没有必要替换Integer topEle minHeap.peek();// 只要当前遍历的元素比堆顶元素大堆顶弹出遍历的元素进去if (nums[i] topEle){minHeap.poll();minHeap.offer(nums[i]);}}return minHeap.peek();}
}python中没有现成的二叉堆要自己实现部分功能 参考https://leetcode.cn/problems/kth-largest-element-in-an-array/solutions/1507044/by-flix-amc8/
2.堆排序原理
排序升序用小降序用大
大顶推 根结点是整个结构最大的元素 将根结点拿走剩下的重排此时根结点就是第二大的元素 再拿走根结点再排 以此类推最后堆中只剩最后一个元素此时拿走的数据也就排好序了
拿走重排的具体过程移除堆顶元素把下标为n的元素放到堆顶再通过堆化的方法将剩下的n-1个元素重新构建成堆
小顶堆与大顶堆类似
3.合并k个排序链表
LeetCode23. 合并 K 个升序链表 https://leetcode.cn/problems/merge-k-sorted-lists/
思路分析 问题有很多种方法现在看使用堆排序如何解决
因为每个队列都是从小到大排序的每次都要找最小的元素所以用小根堆 堆的大小定义给了几个链表堆就定义多大 每次都将剩余节点的最小值加到输出链表尾部然后进行堆调整 最后堆空的时候合并也就完成了。
代码实现
/*** 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) {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;}
}
