LeetCode 703数据流中的第K大元素 HERODING的LeetCode之路

HERODING23 · CSDN · · 2021-02-11 14:16

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/kth-largest-element-in-a-stream
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路：
这道题目需要反复阅读才能够理解真正的意思，就是先初始化一个类保存数组，这个数组只维护排名前K名的数字，允许重复，然后不断添加，不断删除小的元素，所以可以用最小堆或者multiset，允许重复的set，set会自动根据大小进行排序，代码如下：

class KthLargest {
    int K;
    multiset<int> st;
public:
    KthLargest(int k, vector<int>& nums) {
        for (int n : nums) {
            st.insert(n);
            if (st.size() > k) st.erase(st.begin());
        }       
        K = k;
    }
    int add(int val) {
        st.insert(val);
        if (st.size() > K) st.erase(st.begin());
        return *st.begin();
    }
};


/*作者：heroding
链接：https://leetcode-cn.com/problems/kth-largest-element-in-a-stream/solution/zui-xiang-xi-zhu-jie-by-heroding-h195/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。*/

heap代码如下：

class KthLargest {
    int len;
    // 定义堆，根据>排序，即谁大谁在后面，最小堆可以理解为从小到大排序的队列
    priority_queue<int, vector<int>, greater<int>> heap;
public:
    KthLargest(int k, vector<int>& nums) {
        for (auto n : nums) {
            heap.push(n);
            // 如果超出K
            if (heap.size() > k) {
                heap.pop();
            }
        }       
        len = k;
    }
    int add(int val) {
        heap.push(val);
        // 如果超出K
        if (heap.size() > len) {
            heap.pop();
        }
        // 返回堆顶
        return heap.top();
    }
};



/*作者：heroding
链接：https://leetcode-cn.com/problems/kth-largest-element-in-a-stream/solution/zui-xiang-xi-zhu-jie-by-heroding-h195/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。*/

原文地址：访问原文地址
快照地址：访问文章快照

分享到微博