自己搭建个人网站,剪辑培训,英语网站推广策划书,软件工程女生好就业吗数组中的第K个最大元素
问题描述
给定整数数组 nums 和整数 k#xff0c;请返回数组中第 k 个最大的元素。请注意#xff0c;你需要找的是数组排序后的第 k 个最大的元素#xff0c;而不是第 k 个不同的元素。你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。详见le…数组中的第K个最大元素
问题描述
给定整数数组 nums 和整数 k请返回数组中第 k 个最大的元素。请注意你需要找的是数组排序后的第 k 个最大的元素而不是第 k 个不同的元素。你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。详见leetcode215
问题分析
可以创建一个包含k个元素的最小堆初始时将数组元素中的前K个放入堆中之后遍历数组中的其他元素与堆顶元素比较只有大于堆顶元素才将该元素与堆顶元素替换(即先执行删除在执行插入)遍历结束后堆顶元素即是数组中第K大的元素。
代码实现
public int findKthLargest(int[] nums, int k) {if(knums.length){return -1;}PriorityQueueInteger minHeap new PriorityQueue(4, (a, b) - a - b);for(int i0;ik;i){minHeap.offer(nums[i]);}for(int ik;inums.length;i){if(nums[i]minHeap.peek()){minHeap.poll();minHeap.offer(nums[i]);}}return minHeap.poll();
}堆排序
问题描述
给定整数数组nums,使用堆排序对数组中的元素进行排序。
问题分析
使用堆排序对数组元素进行排序
代码实现
public static void heapSort(int[] nums){PriorityQueueInteger minHeap new PriorityQueue(nums.length,(a,b) - a-b);for (int i 0; i nums.length; i) {minHeap.offer(nums[i]);}for (int i 0; i nums.length; i) {nums[i] minHeap.poll();}
}合并K个有序链表
问题描述
给你一个链表数组每个链表都已经按升序排列。请你将所有链表合并到一个升序链表中返回合并后的链表。详见leetcode23
问题分析
链表数组中存放的其实是每个链表的头节点可以根据链表的长度创建相同大小的最小堆将链表中的节点放入堆中之后取堆顶元素即为最小元素并取出元素的下一个元素放入堆中。
代码实现
public ListNode mergeKLists(ListNode[] lists) {PriorityQueueListNode minHeap new PriorityQueueListNode((a,b) - a.val-b.val);for(int i0;ilists.length;i){if(lists[i]!null){minHeap.offer(lists[i]);}}ListNode vhead new ListNode(-1);ListNode iter vhead;while(!minHeap.isEmpty()){ListNode node minHeap.poll();iter.next node;iter node;if(iter.next!null){minHeap.offer(iter.next);}}return vhead.next;
}总结
堆查找和排序的应用主要是指堆排序和查找最大最小元素或者第几大第几小元素的问题上。这里我们遵循的原则是
查找查大用小堆查小用大堆
排序: 升序用小堆降序用大堆
堆的操作过程比较复杂在java中可以使用优先队列实现堆的操作因为java中的优先队列是基于堆实现的。
