面试经典150题 堆

215.数组中的第K个最大元素
建堆算法实现-CSDN博客

215. 数组中的第K个最大元素

中等

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

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

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

示例 1:

输入: 

[3,2,1,5,6,4],

 k = 2
输出: 5

示例 2:

输入:  

[3,2,3,1,2,4,5,5,6], 

k = 4
输出: 4

提示：

• 1 <= k <= nums.length <= 105
• -104 <= nums[i] <= 104

进行建堆操作，每次将堆中的第一个元素（最大元素）执行删除操作，删除K次后，最近一次删除掉的元素即为数组中的第K个最大元素 

        

class Solution {// 找到数组中第 k 大的元素public int findKthLargest(int[] nums, int k) {// 构建初始堆heapify(nums, nums.length);int size = nums.length;// 进行 k 次操作，每次将堆顶元素与末尾元素交换，并调整堆for (int i = 0; i < k; i++) {// 交换堆顶元素和当前末尾元素swap(nums, 0, size - 1);// 调整堆，排除已确定的末尾元素down(nums, 0, --size);}// 返回堆顶元素，即第 k 大的元素return nums[size];}// 构建初始堆的方法private static void heapify(int[] nums, int size) {// 从最后一个非叶子节点开始，逐步调整堆for (int i = size / 2 - 1; i >= 0; i--) {down(nums, i, size);}}// 堆的下潜操作private static void down(int[] array, int parent, int size) {while (true) {int max = parent;int left = parent * 2 + 1;int right = left + 1;// 如果左子节点存在且大于当前最大元素，更新最大元素索引if (left < size && array[left] > array[max]) {max = left;}// 如果右子节点存在且大于当前最大元素，更新最大元素索引if (right < size && array[right] > array[max]) {max = right;}// 如果最大元素就是当前父节点，说明堆调整完成，退出循环if (max == parent) {break;}// 交换最大元素和父节点swap(array, max, parent);// 更新父节点索引，继续调整parent = max;}}// 交换数组中两个元素的方法private static void swap(int[] a, int i, int j) {int temp = a[i];a[i] = a[j];a[j] = temp;}
}

502.IPO
502. IPO

困难

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

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

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

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

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

示例 1：

输入：k = 2, w = 0, profits = [1,2,3], capital = [0,1,1]
输出：4
解释：
由于你的初始资本为 0，你仅可以从 0 号项目开始。
在完成后，你将获得 1 的利润，你的总资本将变为 1。
此时你可以选择开始 1 号或 2 号项目。
由于你最多可以选择两个项目，所以你需要完成 2 号项目以获得最大的资本。
因此，输出最后最大化的资本，为 0 + 1 + 3 = 4。
示例 2：

输入：k = 3, w = 0, profits = [1,2,3], capital = [0,1,2]
输出：6
提示：

1 <= k <= 105
0 <= w <= 109
n == profits.length
n == capital.length
1 <= n <= 105
0 <= profits[i] <= 104
0 <= capital[i] <= 109
理解题意：我们有一个现有的资本，一个所需资本和利润对应的投资元素，我们要进行投资资本就必须大于所需资本，要求K次投资能获得的最大资本。

贪心思想：在所有能投资的项目中，我们投资利润最大的那个。

思路：将资本和利润一一对应后，按照所需资本进行排序。

逐个遍历，将所有能投资的项目放入大根堆中，通过大根堆的性质选出利润最大的那一个进行投资，赚取利润后，再将我们目前能新投资的项目（我们赚取了利润，资本变多了）放入大根堆中，重复这个过程，直到投资的k次机会用完或者没有能投资的项目 

class Solution {// 找到最大化资本的方法public int findMaximizedCapital(int k, int w, int[] profits, int[] capital) {// 创建一个二维数组，用于存储资本和利润信息int total[][] = new int[profits.length][2];for (int i = 0; i < profits.length; i++) {// 将资本存入二维数组的第一列total[i][0] = capital[i];// 将利润存入二维数组的第二列total[i][1] = profits[i];}// 按照资本从小到大对二维数组进行排序Arrays.sort(total, (a, b) -> a[0] - b[0]);// 创建一个大顶堆优先队列，用于存储可选择的最大利润项目PriorityQueue<Integer> pq = new PriorityQueue<>((x, y) -> y - x);int cur = 0;for (int i = 0; i < k; i++) {// 当还有未处理的项目且当前项目的资本小于等于当前资本 w 时while (cur < profits.length && total[cur][0] <= w) {// 将当前项目的利润加入优先队列pq.add(total[cur][1]);cur++;}// 如果优先队列不为空if (!pq.isEmpty()) {// 取出最大利润项目并增加当前资本 ww += pq.poll();} else {// 如果优先队列为空，无法进行操作，退出循环break;}}// 返回最终的资本 wreturn w;}
}

373.查找和最小的K对数字 
373. 查找和最小的 K 对数字

中等

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

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

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

示例 1:

输入: nums1 = [1,7,11], nums2 = [2,4,6], k = 3
输出: [1,2],[1,4],[1,6]
解释: 返回序列中的前 3 对数：
     [1,2],[1,4],[1,6],[7,2],[7,4],[11,2],[7,6],[11,4],[11,6]
示例 2:

输入: nums1 = [1,1,2], nums2 = [1,2,3], k = 2
输出: [1,1],[1,1]
解释: 返回序列中的前 2 对数：
     [1,1],[1,1],[1,2],[2,1],[1,2],[2,2],[1,3],[1,3],[2,3]
提示:

1 <= nums1.length, nums2.length <= 105
-109 <= nums1[i], nums2[i] <= 109
nums1 和 nums2 均为 升序排列
1 <= k <= 104
k <= nums1.length * nums2.length
首先我们明确，最小的数字对一定是nums1[0] + nums2[0],比他们稍大的可能是nums1[0 + 1] + nums2[0]或者nums1[0] + nums2[0 + 1]，这种情况对每一个找到的数字对都适用。

我们优先将nums1[0] + nums2[0]加入小顶堆中，采取循环的方式，每次找到一个最小数字对，就加入所有可能的下一个最小数字对，注意当我们找到的不是第一个最小数字对时（nums1[0] + nums2[0]），堆中所有的元素和新加入的数字对都有可能是下一个最小数字对。

注意这里有一个特殊情况，看例子2，我们所找到的数字对，元素可能是相同的，但是索引不能是相同的，而我们在加入数字对的过程中，可能加入索引相同的数字对，造成重复的情况，所以我们要使用hash进行去重，如果找到的数字对的索引我们已经使用过了，我们就不能把他们对应的元素加入结果数组中，去重后k++，因为我们没有找到一个新的最小数字对。

class Solution {public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {// 创建一个优先队列，用于存储二元组，按照两数之和的大小进行排序PriorityQueue<int[]> pq = new PriorityQueue<>(k, (o1, o2) -> {return nums1[o1[0]] + nums2[o1[1]] - nums1[o2[0]] - nums2[o2[1]];});// 用于存储最终结果的列表List<List<Integer>> result = new ArrayList<>();int length1 = nums1.length;int length2 = nums2.length;// 如果任一数组为空，直接返回空结果列表if (length1 == 0 || length2 == 0) {return result;}// 将第一个二元组（0,0）加入优先队列pq.offer(new int[]{0, 0});// 创建一个哈希表，用于存储已经处理过的二元组列表HashMap<List<Integer>, Integer> map = new HashMap<>();// 循环直到 k 次或者优先队列为空while (k-- > 0 &&!pq.isEmpty()) {// 取出优先队列中的二元组int[] temp = pq.poll();// 创建一个临时列表，存储当前二元组的索引List<Integer> mapList = new ArrayList<>();mapList.add(temp[0]);mapList.add(temp[1]);// 如果该二元组已经处理过，增加 k 的值，继续下一次循环if (map.containsKey(mapList)) {k++;continue;}// 将当前二元组列表加入哈希表map.put(mapList, 0);// 创建一个列表，存储当前二元组对应的两个数List<Integer> list = new ArrayList<>();list.add(nums1[temp[0]]);list.add(nums2[temp[1]]);// 将当前二元组对应的两个数的列表加入结果列表result.add(list);// 如果第一个数组还有下一个元素，将下一个二元组加入优先队列if (temp[0] + 1 < length1) {pq.offer(new int[]{temp[0] + 1, temp[1]});}// 如果第二个数组还有下一个元素，将下一个二元组加入优先队列if (temp[1] + 1 < length2) {pq.offer(new int[]{temp[0], temp[1] + 1});}}// 返回最终结果列表return result;}
}