个人任务15.数据流的第 K 大数值

﹏ヽ暗。殇╰゛Y 2023-09-28 13:33 70阅读 0赞

作者: Turbo 时间限制: 1S 章节: 课程设计

> **问题描述 :**  
> 设计一个找到数据流中第 k 大元素的类（class）。注意是排序后的第 k 大元素，不是第 k 个不同的元素。  
> 请实现 KthLargest 类：  
> KthLargest(int k, int\[\] nums) 使用整数 k 和整数流 nums 初始化对象。  
> int add(int val) 将 val 插入数据流 nums 后，返回当前数据流中第 k 大的元素。  
> 示例：  
> 输入：  
> 3 4  
> 4 5 8 2  
> add 3  
> add 5  
> add 10  
> add 9  
> add 4  
> 输出：  
> 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

> **输入说明 :**  
> 输入若干行:  
> 首行输入两个整数k和n，k代表题中的k，n代表用来初始化对象的nums数组的长度。  
> 第二行输入n个整数代表用来初始化对象的数组nums的元素。  
> 后面若干行输入 add 指令，每个add后面跟一个整数表示val。  
> 提示：  
> 1 <= k <= 10^4  
> 0 <= n <= 10^4  
> \-10^4 <= nums\[i\] <= 10^4  
> \-10^4 <= val <= 10^4  
> 最多调用 add 方法 10^4 次  
> 题目数据保证，在查找第 k 大元素时，数组中至少有 k 个元素

> **输出说明 :**  
> 输出若干行，每行一个整数，为add指令的返回值。

> **输入范例 :**  
> 2 4  
> 3 5 7 6  
> add 5  
> add 4  
> add 8

> **输出范例 :**  
> 6  
> 6  
> 7

#include<iostream>
    #include<vector>
    #include<string>
    #include<sstream>
    #include<queue>
    #include<stack>
    #include<cmath>
    #include<algorithm>
    #include<cstring>
    #include<stdlib.h>
    #include<stdio.h>
    #include<fstream>
    #include<iomanip>
    #include<utility>
    using namespace std;
    int a[10001]={
        0},b[10001]={
        0};
    
    class KthLargest{
        
    public:
        priority_queue<int,vector<int>,greater<int> > q;
        int k;
        KthLargest(int k,vector<int>& nums) {
        
            this->k=k;
            for(auto& x: nums){
        
                add(x);
            }
        }
        int add(int val){
        
            q.push(val);
            if(q.size()>k)
                q.pop();
            return q.top();
        }
    };
    
    int main(){
        
        int n,k,x;
        cin>>k>>n;
        vector<int> v;
        for(int i=0;i<n;++i){
        
            cin>>x;
            v.push_back(x);
        }
        string s;
        KthLargest kx(k,v);
        while(scanf("%s",&s[0])!=EOF){
        
            cin>>x;
            cout<<kx.add(x)<<endl;
        }
        return 0;
    }