leetcode 703. 数据流中的第K大元素小顶堆

àì夳堔傛蜴生んèń 2023-06-12 04:12 7阅读 0赞

**建立一个大小为k的最小堆，堆顶就是第k大的元素  
数据流中如果有比k大的元素，入堆，重新调整，保持一共k个元素  
如果比k小直接返回堆顶即可**

#include <iostream>
    #include <vector>
    #include <algorithm>
    #include <functional>
    
    using namespace std;
    
    #define debug(x) cout<<#x<<": "<<x<<endl;
    
    class KthLargest { 
    public:
        vector<int> numss;
        int kk;
        KthLargest(int k, vector<int>& nums) { 
            kk = k;
            numss = nums;
            make_heap(numss.begin(),numss.end(),greater<int>()  );
            while( numss.size()>kk ){ 
                pop_heap(numss.begin(),numss.end(),greater<int>()  );
                numss.pop_back();
            }
        }
    
        int add(int val) { 
            if( numss.size() < kk ){ 
                numss.push_back( val );
                make_heap(numss.begin(),numss.end(),greater<int>()  );
                return numss[0];
            }else if( val <= numss[0] ){ 
                return numss[0];
            }else{ 
                numss.push_back( val );
                pop_heap(numss.begin(),numss.end(),greater<int>()  );
                numss.pop_back();
                return numss[0];
            }
            return 0;
        }
    };
    
    
    int main()
    { 
        int k = 3;
        vector<int> arr = { 4,5,8,2};
        KthLargest kthLargest(k,arr);
    
        debug( kthLargest.add(3) ); // returns 4
        debug( kthLargest.add(5) );// returns 5
        debug( kthLargest.add(10) );// returns 5
        debug( kthLargest.add(9) );// returns 8
        debug( kthLargest.add(4) );// returns 8
    
        return 0;
    }

![在这里插入图片描述][20191031110950948.png]

[20191031110950948.png]: /images/20230531/04693f1ce75f4ec196a5508ee6565adb.png