原文链接: https://leetcode-cn.com/problems/jBjn9C

中文题目

设计一个找到数据流中第 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/

通过代码

高赞题解

最小堆

此问题属于 topK 问题，是一类典型的题目。处理此类问题最直观的想法就是排序，但是使用排序并不是高效的方法，因为题目只关心第 k 大的数字并且数据是动态的，排序处理时间复杂度太高。堆就是解决一个动态数据集合中的 topK 问题的利器。最小堆经常用来求取数据集合中 k 个值最大的元素，而最大堆经常用来求取数据集合中 k 个值最小的元素。这道题使用最小堆来实现，C ++ 中存在堆的实现

• 默认最大堆 ： priority_queue big_heap
• 最小堆 ： priority_queue<int, vector, greater> small_heap

堆的插入和删除操作的时间复杂度均为 O(logk)，完整代码如下。

class KthLargest {
private:
    priority_queue<int, vector<int>, greater<int>> heap;
    int size;
public:
    KthLargest(int k, vector<int>& nums) {
        size = k;
        for (auto& num : nums) {
            if (heap.size() < size) {
                heap.push(num);
            }
            else if (num > heap.top()) {
                heap.pop();
                heap.push(num);
            }
        }
    }
    
    int add(int val) {
        if (heap.size() < size) {
            heap.push(val);
        }
        else if (val > heap.top()) {
            heap.pop();
            heap.push(val);
        }
        return heap.top();
    }
};

另外感谢@aikez同学指出可以在 KthLargest 函数中调用 add 函数减少代码量。

class KthLargest {
private:
    priority_queue<int, vector<int>, greater<int>> heap;
    int size;
public:
    KthLargest(int k, vector<int>& nums) {
        size = k;
        for (auto& num : nums) {
            add(num);
        }
    }
    
    int add(int val) {
        if (heap.size() < size) {
            heap.push(val);
        }
        else if (val > heap.top()) {
            heap.pop();
            heap.push(val);
        }
        return heap.top();
    }
};

统计信息

通过次数	提交次数	AC比率
3391	5375	63.1%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言