案例

数组中的第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

解题思路

https://leetcode.cn/problems/kth-largest-element-in-an-array/solutions/836425/xie-gei-qian-duan-tong-xue-de-ti-jie-yi-kt5p2

Kapture 2024-08-12 at 10.37.00

// 整个流程就是上浮下沉
var findKthLargest = function (nums, k) {
    let heapSize = nums.length
    buildMaxHeap(nums, heapSize) // 构建好了一个大顶堆
    // 进行下沉 大顶堆是最大元素下沉到末尾
    for (let i = nums.length - 1; i >= nums.length - k + 1; i--) {
        swap(nums, 0, i)
        --heapSize // 下沉后的元素不参与到大顶堆的调整
        // 重新调整大顶堆
        maxHeapify(nums, 0, heapSize);
    }
    return nums[0]
    // 自下而上构建一颗大顶堆
    function buildMaxHeap(nums, heapSize) {
        for (let i = Math.floor(heapSize / 2) - 1; i >= 0; i--) {
            maxHeapify(nums, i, heapSize)
        }
    }
    // 从左向右，自上而下的调整节点
    function maxHeapify(nums, i, heapSize) {
        let l = i * 2 + 1
        let r = i * 2 + 2
        let 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) // 进行节点调整
            // 继续调整下面的非叶子节点
            maxHeapify(nums, largest, heapSize)
        }
    }
    function swap(a, i, j) {
        let temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
};

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

解题思路

IPO（Initial Public Offering）算法的问题是在给定初始资金和最大项目数的情况下，从一系列项目中选择项目以最大化最终资金。这个问题可以通过贪心算法来解决，其核心思路是每次选择当前可用的最大利润项目。

以下是IPO算法的步骤总结：

1. 数据准备：首先，将所有项目按照启动资金需求排序。这样可以确保我们在选择项目时，总是先考虑那些我们能够承担得起的项目。
2. 初始化优先队列：创建一个最大优先队列（或最大堆）来存储当前可用的最大利润项目。最大优先队列的特点是每次都能在O(log n)的时间内取出当前队列中的最大值。
3. 选择项目：遍历排序后的项目列表，将当前资金能够启动的项目加入最大优先队列。然后，从队列中取出最大利润项目，并更新当前资金。重复这个过程，直到完成k个项目或没有更多项目可做。
4. 返回结果：返回最终的资本，即初始资金加上通过选择项目获得的利润。

IPO算法的关键在于使用最大优先队列来有效地选择最大利润项目，这样可以确保每次选择都是当前情况下的最优选择，从而最大化最终资金。

// 定义一个最大优先队列类
class MaxPriorityQueue {
    constructor() {
        this.heap = []; // 初始化堆数组
    }

    // 向堆中添加一个元素
    enqueue(val) {
        this.heap.push(val); // 将元素添加到堆的末尾
        this.bubbleUp(this.heap.length - 1); // 将新添加的元素上浮到正确的位置
    }

    // 从堆中删除并返回最大元素
    dequeue() {
        if (this.heap.length === 0) return null; // 如果堆为空，返回null
        const max = this.heap[0]; // 暂存堆顶元素
        const end = this.heap.pop(); // 删除堆顶元素，并获取堆的最后一个元素
        if (this.heap.length > 0) {
            this.heap[0] = end; // 将最后一个元素移动到堆顶
            this.sinkDown(0); // 将新堆顶元素下沉到正确的位置
        }
        return max; // 返回暂存的堆顶元素
    }

    // 检查堆是否为空
    isEmpty() {
        return this.heap.length === 0; // 如果堆数组长度为0，返回true，否则返回false
    }

    // 上浮操作，用于将新添加的元素移动到正确的位置
    bubbleUp(index) {
        const parent = Math.floor((index - 1) / 2); // 计算父节点的索引
        if (index > 0 && this.heap[index] > this.heap[parent]) {
            // 如果当前元素大于父节点，交换它们的位置
            [this.heap[index], this.heap[parent]] = [this.heap[parent], this.heap[index]];
            this.bubbleUp(parent); // 递归地对父节点执行上浮操作
        }
    }

    // 下沉操作，用于将新堆顶元素移动到正确的位置
    sinkDown(index) {
        const left = 2 * index + 1; // 计算左子节点的索引
        const right = 2 * index + 2; // 计算右子节点的索引
        let largest = index; // 初始化最大元素的索引为当前索引

        if (left < this.heap.length && this.heap[left] > this.heap[largest]) {
            // 如果左子节点存在且大于当前元素，更新最大元素的索引
            largest = left;
        }

        if (right < this.heap.length && this.heap[right] > this.heap[largest]) {
            // 如果右子节点存在且大于当前元素，更新最大元素的索引
            largest = right;
        }

        if (largest !== index) {
            // 如果最大元素的索引不是当前索引，交换它们的位置
            [this.heap[index], this.heap[largest]] = [this.heap[largest], this.heap[index]];
            this.sinkDown(largest); // 递归地对新的最大元素执行下沉操作
        }
    }
}

// IPO算法函数
function findMaximizedCapital(k, w, profits, capital) {
    const n = profits.length; // 获取项目的数量
    const list = []; // 初始化项目列表
    for (let i = 0; i < n; i++) {
        list.push([capital[i], profits[i]]); // 将项目和其启动资金需求添加到列表中
    }
    list.sort((a, b) => a[0] - b[0]); // 根据启动资金需求对项目进行排序

    const maxHeap = new MaxPriorityQueue(); // 创建一个最大优先队列
    let i = 0; // 初始化项目索引

    while (k-- > 0) { // 循环k次，每次选择一个项目
        while (i < n && list[i][0] <= w) {
            // 将当前资金能做的项目加入优先队列
            maxHeap.enqueue(list[i++][1]);
        }
        if (maxHeap.isEmpty()) break; // 如果优先队列为空，没有更多项目可做，退出循环
        w += maxHeap.dequeue(); // 选择利润最大的项目，并更新资金
    }

    return w; // 返回最终的资本
}

查找和最小的 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

解题思路

1. 初始化一个空数组res来存储结果。
2. 创建一个最小优先队列pq，其比较函数是两个数组的元素之和。这里使用了compare函数来定义优先队列的顺序，compare函数返回true时，表示第一个参数应该排在第二个参数前面。
3. 遍历nums1的前k个元素（如果nums1的长度小于k，则遍历整个数组），将每个元素与nums2的第一个元素的索引组合加入优先队列。
4. 当res的长度小于k且优先队列不为空时，从队列中取出最小元素，将其加入res数组。
5. 如果取出的元素的nums2索引加1小于nums2的长度，则将这个元素与nums2的下一个元素的索引组合加入优先队列。
6. 重复步骤4和5，直到res的长度达到k或优先队列为空。

// 定义一个函数 kSmallestPairs，接受三个参数：两个数组 nums1 和 nums2，以及一个整数 k
var kSmallestPairs = function (nums1, nums2, k) {
    const res = []; // 初始化一个空数组来存储结果
    // 创建一个最小优先队列 pq，其比较函数是两个数组的元素之和
    // 比较函数用于确定优先队列中元素的顺序，返回值小于0时，第一个参数排在第二个参数前面
    const pq = new MinPriorityQueue({ compare: (a, b) => nums1[a[0]] + nums2[a[1]] - (nums1[b[0]] + nums2[b[1]]) });

    // 遍历 nums1 的前 k 个元素（如果 nums1 的长度小于 k，则遍历整个数组）
    // 将每个元素与 nums2 的第一个元素的索引组合加入优先队列
    for (let i = 0; i < Math.min(k, nums1.length); i++) pq.enqueue([i, 0]);

    // 当 res 的长度小于 k 且优先队列不为空时，继续执行
    while (res.length < k && pq.size()) {
        const [i, j] = pq.dequeue(); // 从队列中取出最小元素
        // 如果取出的元素的 nums2 索引加1小于 nums2 的长度，则将这个元素与 nums2 的下一个元素的索引组合加入优先队列
        if (j + 1 < nums2.length) pq.enqueue([i, j + 1]);
        res.push([nums1[i], nums2[j]]); // 将这个元素加入结果数组
    }

    return res; // 返回结果数组
};

数据流的中位数（难）

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

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

实现 MedianFinder 类:

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

示例 1：

输入
["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"]
[[], [1], [2], [], [3], []]
输出
[null, null, null, 1.5, null, 2.0]

解释
MedianFinder medianFinder = new MedianFinder();
medianFinder.addNum(1);    // arr = [1]
medianFinder.addNum(2);    // arr = [1, 2]
medianFinder.findMedian(); // 返回 1.5 ((1 + 2) / 2)
medianFinder.addNum(3);    // arr[1, 2, 3]
medianFinder.findMedian(); // return 2.0

提示:

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

解题思路

1. 初始化两个堆： 创建一个最小堆（A）和一个最大堆（B）。最小堆（A）用于存储较大的那一半元素，最大堆（B）用于存储较小的那一半元素。
2. 添加元素： 当新元素到来时，我们将其添加到其中一个堆中，然后从该堆中取出堆顶元素并添加到另一个堆中。这样做的目的是保持两个堆的大小平衡，或者使它们的大小差不超过1。
   • 如果A和B的大小相同，我们将新元素添加到B（最大堆）中，然后从B中取出最大的元素（堆顶元素）放入A（最小堆）中。
   • 如果A和B的大小不同，我们将新元素添加到A（最小堆）中，然后从A中取出最小的元素（堆顶元素）放入B（最大堆）中。
3. 查找中位数： 当我们需要查找中位数时，根据两个堆的大小，我们可以确定中位数是哪个堆的堆顶元素，或者是两个堆顶元素的平均值。
   • 如果A和B的大小相同，中位数是两个堆顶元素的平均值。
   • 如果A和B的大小不同，中位数是A（最小堆）的堆顶元素。

const { MinPriorityQueue, MaxPriorityQueue } = require('priority-queue');

class MedianFinder {
    constructor() {
        this.A = new MinPriorityQueue(); // 最小堆，保存较大的一半
        this.B = new MaxPriorityQueue(); // 最大堆，保存较小的一半
    }

    addNum(num) {
        // 如果A和B的大小相同，将新元素添加到B，然后从B取出最大元素放入A
        if (this.A.size() === this.B.size()) {
            this.B.enqueue(num);
            this.A.enqueue(this.B.dequeue().element);
        } else {
            // 如果A和B的大小不同，将新元素添加到A，然后从A取出最小元素放入B
            this.A.enqueue(num);
            this.B.enqueue(this.A.dequeue().element);
        }
    }

    findMedian() {
        // 如果A和B的大小相同，中位数是两个堆顶元素的平均值
        // 如果A和B的大小不同，中位数是A的堆顶元素
        return this.A.size() !== this.B.size() ? this.A.front().element : (this.A.front().element + this.B.front().element) / 2.0;
    }
}