跳到主要内容

剑指 Offer II 059.数据流的第 K 大数值

· 阅读需 4 分钟

1、题干​

设计一个找到数据流中第 k 大元素的类（class）。注意是排序后的第 k 大元素，不是第 k 个不同的元素。

请实现 KthLargest 类：

  • KthLargest(int k, int[] nums) 使用整数 k 和整数流 nums 初始化对象。
  • int add(int val) 将 val 插入数据流 nums 后，返回当前数据流中第 k 大的元素。

 

示例：

输入：
["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);   // return 4
kthLargest.add(5);   // return 5
kthLargest.add(10);  // return 5
kthLargest.add(9);   // return 8
kthLargest.add(4);   // return 8

 

提示：

  • 1 <= k <= 104
  • 0 <= nums.length <= 104
  • -104 <= nums[i] <= 104
  • -104 <= val <= 104
  • 最多调用 add 方法 104 次
  • 题目数据保证，在查找第 k 大元素时，数组中至少有 k 个元素

 

注意：本题与主站 703 题相同： https://leetcode-cn.com/problems/kth-largest-element-in-a-stream/

2、解法1-优先队列​

使用优先队列解题，初始化时把所有元素加入到最小优先队列pq中，添加元素时直接把元素加入pq，若pq元素个数小于k则直接返回-1，若pq元素个数超过k则逐一移除最后返回队头元素。


3、代码​

var KthLargest = function (k, nums) {
    this.k = k;
    this.pq = new MinPriorityQueue({ compare: (a, b) => a - b });
    for (const n of nums) this.pq.enqueue(n);
};

KthLargest.prototype.add = function (val) {
    this.pq.enqueue(val);
    if (this.pq.size() < this.k) return -1;
    while (this.pq.size() > this.k) this.pq.dequeue();
    return this.pq.front();
};

4、复杂度​

  • 时间复杂度：O(nlogn)O(nlogn)
  • 空间复杂度：O(n)O(n)

5、执行结果​

执行用时: 132 ms 内存消耗: 46.6 MB


6、解法2-计数排序​

对数据流使用计数排序，首次确定第 k 大元素 kIdx 需要遍历所有元素；此后添加数据需要再确定第 k 大元素时，如果添加的数据比 kIdx 小则直接返回 kIdx ；如果添加的数据比 kIdx 小则从下标 kIdx 开始在容器 list 找到更大且元素值不为0的下标返回即可。


这个题目中使用该算法坑略多，只作参考，不建议使用。


7、复杂度​

  • 时间复杂度：O(n)O(n)
  • 空间复杂度：O(n)O(n)

8、代码​

var KthLargest = function (k, nums) {
    this.k = k;
    this.size = nums.length;
    this.kIdx = -1;
    this.list = new Array(2e4 + 1).fill(0);
    for (const n of nums) this.list[n + 1e4]++;
};

KthLargest.prototype.add = function (val) {
    (val += 1e4), this.list[val]++, this.size++;
    if (this.size < this.k) return -1;

    if (this.kIdx < 0) {
        for (let i = this.list.length - 1, k = this.k; i >= 0; i--) {
            if (k < this.list[i]) this.list[i] = k;
            if ((k -= this.list[i]) <= 0) {
                this.kIdx = i;
                break;
            }
        }
        return this.kIdx - 1e4;
    }

    if (this.size > this.k && val >= this.kIdx) {
        this.list[this.kIdx]--;
        for (let i = this.kIdx; i < this.list.length; i++) {
            if (this.list[i]) {
                this.kIdx = i;
                break;
            }
        }
    }

    return this.kIdx - 1e4;
};

9、执行结果​

1.png