学习记录：js算法（六十三）：数据流中的第 K 大元素

数据流中的第 K 大元素

设计一个找到数据流中第 k 大元素的类（class）。注意是排序后的第 k 大元素，不是第 k 个不同的元素。
请实现 KthLargest 类：
KthLargest(int k, int[] nums) 使用整数 k 和整数流 nums 初始化对象。
int add(int val) 将 val 插入数据流 nums 后，返回当前数据流中第 k 大的元素。

示例 1：
输入：
["KthLargest", "add", "add", "add", "add", "add"]
[[3, [4, 5, 8, 2]], [3], [5], [10], [9], [4]]
输出：[null, 4, 5, 5, 8, 8]
解释：
KthLargest kthLargest = new KthLargest(3, [4, 5, 8, 2]);
kthLargest.add(3); // 返回 4
kthLargest.add(5); // 返回 5
kthLargest.add(10); // 返回 5
kthLargest.add(9); // 返回 8
kthLargest.add(4); // 返回 8


示例 2：
输入：
["KthLargest", "add", "add", "add", "add"]
[[4, [7, 7, 7, 7, 8, 3]], [2], [10], [9], [9]]
输出：[null, 7, 7, 7, 8]
解释：
KthLargest kthLargest = new KthLargest(4, [7, 7, 7, 7, 8, 3]);
kthLargest.add(2); // 返回 7
kthLargest.add(10); // 返回 7
kthLargest.add(9); // 返回 7
kthLargest.add(9); // 返回 8

思路一

class MinHeap {
    constructor() {
        this.heap = [];
    }

    insert(val) {
        this.heap.push(val);
        this.bubbleUp(this.heap.length - 1);
    }

    bubbleUp(index) {
        while (index > 0) {
            let parent = Math.floor((index - 1) / 2);
            if (this.heap[parent] <= this.heap[index]) break;
            [this.heap[parent], this.heap[index]] = [this.heap[index], this.heap[parent]];
            index = parent;
        }
    }

    extractMin() {
        const min = this.heap[0];
        this.heap[0] = this.heap.pop();
        this.bubbleDown(0);
        return min;
    }

    bubbleDown(index) {
        while (true) {
            let leftChild = 2 * index + 1;
            let rightChild = 2 * index + 2;
            let smallest = index;

            if (leftChild < this.heap.length && this.heap[leftChild] < this.heap[smallest]) {
                smallest = leftChild;
            }
            if (rightChild < this.heap.length && this.heap[rightChild] < this.heap[smallest]) {
                smallest = rightChild;
            }
            if (smallest === index) break;

            [this.heap[smallest], this.heap[index]] = [this.heap[index], this.heap[smallest]];
            index = smallest;
        }
    }
}

class KthLargest {
    constructor(k, nums) {
        this.k = k;
        this.minHeap = new MinHeap();
        nums.forEach(num => this.minHeap.insert(num));
        while (this.minHeap.heap.length > k) {
            this.minHeap.extractMin();
        }
    }

    add(val) {
        if (this.minHeap.heap.length < this.k) {
            this.minHeap.insert(val);
        } else if (val > this.minHeap.heap[0]) {
            this.minHeap.insert(val);
            this.minHeap.extractMin();
        }
        return this.minHeap.heap[0];
    }
}

讲解
为了设计这样一个类，我们可以使用最小堆（优先队列）来实现。
最小堆是一种特殊的完全二叉树，其中每个父节点的值都小于或等于其子节点的值。
在本问题中，我们维护一个大小为 k 的最小堆，这样堆顶元素就是当前数据流中的第k大元素。
每次插入新元素时，若堆的大小未达到 k ，则直接将新元素添加到堆中；若堆的大小已经达到 k ，且新元素大于堆顶元素，则替换堆顶元素并重新调整堆。这样，堆顶元素始终是当前数据流中的第 k 大元素。

思路二

class KthLargest {
    constructor(k, nums) {
        this.k = k;
        this.minHeap = []; // 最小堆
        for (let num of nums) {
            this.add(num); // 初始化时添加所有元素
        }
    }

    add(val) {
        // 将新值添加到堆中
        this.minHeap.push(val);
        // 维护最小堆的性质
        this.minHeap.sort((a, b) => a - b); // 排序以维护堆
        // 如果堆的大小超过 k，移除最小元素
        if (this.minHeap.length > this.k) {
            this.minHeap.shift(); // 移除最小元素
        }
        // 返回当前第 k 大的元素
        return this.minHeap[0]; // 返回堆的根元素
    }
}

讲解

1. 构造函数 KthLargest(int k, int[] nums)：、
   • 初始化类的实例，设置 k 和最小堆 minHeap。
   • 遍历 nums 数组，将每个元素添加到堆中。
2. 方法 add(int val) :
   • 将新值 val 添加到堆中。
   • 使用 sort 方法对堆进行排序，确保最小元素在堆顶。
   • 检查堆的大小，如果超过 k，则移除最小元素（堆顶）。
   • 返回堆的根元素，即当前数据流中的第 k 大元素。

原文地址：https://blog.csdn.net/weixin_48677331/article/details/142899774

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！