面试经典150题——堆

---

1、数组中的第K个最大元素

1.1 题目链接

点击跳转到题目位置

1.2 题目描述

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。

请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

提示：

• 1 <= k <= nums.length <= 10⁵
• -10⁴ <= nums[i] <= 10⁴

1.3 解题代码

class Solution {public int findKthLargest(int[] nums, int k) {int heapSize = nums.length;bulidMaxHeap(nums, heapSize);for(int i = nums.length - 1; i >= nums.length - k + 1; --i){swap(nums, 0, i);--heapSize;maxHeapipy(nums, 0, heapSize);}return nums[0];}public void bulidMaxHeap(int[] nums, int heapSize){for(int i =  heapSize / 2 - 1; i >= 0; --i){maxHeapipy(nums, i, heapSize);}}public void maxHeapipy(int[] nums, int i, int heapSize){int l = i * 2 + 1, r = i * 2 + 2, largest = i;if(l < heapSize && nums[l] > nums[largest]){largest = l;}if(r < heapSize && nums[r] > nums[largest]){largest = r;}if(largest != i){swap(nums, i, largest);maxHeapipy(nums, largest, heapSize);}}public void swap(int[] nums, int i, int j){int temp = nums[i];nums[i] = nums[j];nums[j] = temp;}
}

1.4 解题思路

1. 建立大根堆。

2、IPO

2.1 题目链接

点击跳转到题目位置

2.2 题目描述

假设 力扣（LeetCode）即将开始 IPO 。为了以更高的价格将股票卖给风险投资公司，力扣 希望在 IPO 之前开展一些项目以增加其资本。 由于资源有限，它只能在 IPO 之前完成最多 k 个不同的项目。帮助 力扣 设计完成最多 k 个不同项目后得到最大总资本的方式。

给你 n 个项目。对于每个项目 i ，它都有一个纯利润 profits[i] ，和启动该项目需要的最小资本 capital[i] 。

最初，你的资本为 w 。当你完成一个项目时，你将获得纯利润，且利润将被添加到你的总资本中。

总而言之，从给定项目中选择 最多 k 个不同项目的列表，以 最大化最终资本 ，并输出最终可获得的最多资本。

答案保证在 32 位有符号整数范围内。

提示：

• 1 <= k <= 10⁵
• 0 <= w <= 10⁹
• n == profits.length
• n == capital.length
• 1 <= n <= 10⁵
• 0 <= profits[i] <= 10⁴
• 0 <= capital[i] <= 10⁹

2.3 解题代码

class Solution {public int findMaximizedCapital(int k, int w, int[] profits, int[] capital) {int res = w;int n = profits.length;int[][] nums = new int[n][2];for(int i = 0; i < n; ++i){nums[i][0] = profits[i];nums[i][1] = capital[i];}Arrays.sort(nums, (a, b) -> a[1] - b[1]);PriorityQueue<Integer> pq = new PriorityQueue<>((x , y) -> y - x);int idx = 0;while(idx < n && w >= nums[idx][1]){pq.offer(nums[idx][0]);idx++;}while(k > 0 && !pq.isEmpty()){k--;int num = pq.poll();res += num;w += num;while(idx < n && w >= nums[idx][1]){pq.offer(nums[idx][0]);idx++;}}return res;}
}

2.4 解题思路

1. 创建一个二维数组，存入每一个项目的利润和成本。并且将该二维数组按照成本非递减进行排序。
2. 创建一个大根堆，利润高的项目在堆顶。
3. 初始化最终利润为本金，每次取项目前现将满足条件（成本小于等于当前记录的最终利润）的项目放入大根堆中，每次取项目取栈顶即可。

3、查找和最小的 K 对数字

3.1 题目链接

点击跳转到题目位置

3.2 题目描述

给定两个以 非递减顺序排列 的整数数组 nums1 和 nums2 , 以及一个整数 k 。

定义一对值 (u,v)，其中第一个元素来自 nums1，第二个元素来自 nums2 。

请找到和最小的 k 个数对 (u1,v1), (u2,v2) … (uk,vk) 。

提示:

• 1 <= nums1.length, nums2.length <= 10⁵
• -10⁹ <= nums1[i], nums2[i] <= 10⁹
• nums1 和 nums2 均为 升序排列
• 1 <= k <= 10⁴
• k <= nums1.length * nums2.length

3.3 解题代码

class Solution {public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {List<List<Integer>> res = new ArrayList<>();PriorityQueue<int []> pq = new PriorityQueue<>(k, (o1, o2)->{return nums1[o1[0]] + nums2[o1[1]] - nums1[o2[0]] - nums2[o2[1]];});int m = nums1.length;int n = nums2.length;for(int i = 0; i < Math.min(m, k); ++i){pq.offer(new int[]{i, 0});}while(!pq.isEmpty() && k > 0){k--;int[] idxPair = pq.poll();List list = new ArrayList<>();list.add(nums1[idxPair[0]]);list.add(nums2[idxPair[1]]);res.add(list);if(idxPair[1] < n - 1){pq.offer(new int[]{idxPair[0], idxPair[1] + 1});}}return res;}
}

3.4 解题思路

1. 贪心+优先队列。
2. 优先队列以小根堆的形式，存放的数对下标，其对应的数对值最小的则在堆顶。设m为nums1数组的长度，n为nums2数组的长度，则先取的数对，第一个元素为nums1中前k（m）个元素（如果不足k个取m个）。
3. 然后开始根据优先队列中的堆顶来取元素，记堆顶元素下标对为（x, y），则可能比堆里面的数小的数对中，最小的是{nums1[x], nums2[y + 1]} (只要y小于n - 1)。

4、数据流的中位数

4.1 题目链接

点击跳转到题目位置

4.2 题目描述

中位数是有序整数列表中的中间值。如果列表的大小是偶数，则没有中间值，中位数是两个中间值的平均值。

• 例如 arr = [2,3,4] 的中位数是 3 。
• 例如 arr = [2,3] 的中位数是 (2 + 3) / 2 = 2.5 。
• 实现 MedianFinder 类:

实现 MedianFinder 类:

• MedianFinder() 初始化 MedianFinder 对象。
• void addNum(int num) 将数据流中的整数 num 添加到数据结构中。
• double findMedian() 返回到目前为止所有元素的中位数。与实际答案相差 10^-5 以内的答案将被接受。

提示:

• -10⁵ <= num <= 10⁵
• 在调用 findMedian 之前，数据结构中至少有一个元素
• 最多 5 * 10⁴ 次调用 addNum 和 findMedian

4.3 解题代码

class MedianFinder {PriorityQueue<Integer> maxQueue;// 大根堆PriorityQueue<Integer> minQueue;// 小根堆public MedianFinder() {// 保证大根堆中的元素数量大于等于小根堆中的元素数量maxQueue = new PriorityQueue<>(Comparator.reverseOrder());// 大根堆minQueue = new PriorityQueue<>();// 小根堆}public void addNum(int num) {if(maxQueue.isEmpty() || num <= maxQueue.peek()){maxQueue.offer(num);while(maxQueue.size() > minQueue.size() + 1){minQueue.offer(maxQueue.poll());}} else{minQueue.offer(num);while(maxQueue.size() < minQueue.size()){maxQueue.offer(minQueue.poll());}}}public double findMedian() {if(maxQueue.size() > minQueue.size()){// 优先队列中元素总和为return maxQueue.peek();} else{return (maxQueue.peek() + minQueue.peek()) / 2.0;}}
}/*** Your MedianFinder object will be instantiated and called as such:* MedianFinder obj = new MedianFinder();* obj.addNum(num);* double param_2 = obj.findMedian();*/

4.4 解题思路

1. 用优先队列维持两个堆，一个为大根堆，一个为小根堆，保证大根堆中的元素数量大于等于小根堆中元素的数量，并且最多只能多出一个。
2. 建两个堆是为了保证，大根堆中的元素都小于等于小根堆中的元素，如果元素总数为奇数的话，中位数就是大根堆的堆顶元素，如果为偶数的话，则是大根堆和小根堆堆顶的元素和取平均值。
3. 对于插入数字而言，如果插入时大根堆为空或者插入的数小于等于大根堆的堆顶，则插入小根堆中（不影响两个堆的堆顶），此时如果大根堆的堆顶元素数量大于小根堆堆顶的元素数 + 1，则将大根堆的堆顶插入到小根堆中；如果插入时插入的数大于大根堆的堆顶，则插入小根堆中，如果大根堆中的元素个数小于小根堆中的元素个数，则将小根堆的堆顶插入进入大根堆中。