面试经典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 <= 1050 <= w <= 109n == profits.lengthn == capital.length1 <= n <= 1050 <= profits[i] <= 1040 <= 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()) {
// 取出最大利润项目并增加当前资本 w
w += pq.poll();
} else {
// 如果优先队列为空，无法进行操作，退出循环
break;
}
}
// 返回最终的资本 w
return 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] <= 109nums1和nums2均为 升序排列1 <= k <= 104k <= 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;
}
}