剑指 Offer II 堆

059. 数据流的第 K 大数值

class KthLargest {
public:
priority_queue,greater>heap;//小根堆 维护第1大到第k大的数 top就是第k大的数
int k;//太妙了 
/*
第n大 n-1 n-2 ... k   k-1 k-2 ... 第1大
如果加的数小于a[k]  它将被弹走
         大          k是第k+1大的 把k弹出去 
*/
    KthLargest(int _k, vector& nums) {
        k=_k;
        for(auto x:nums)
        {
            heap.push(x);
            if(heap.size()>k)heap.pop();
        }
    }
    int add(int val) {
         heap.push(val);
            if(heap.size()>k)heap.pop();
            return heap.top();
    }
};

060. 出现频率最高的 k 个数字

class Solution {
public:
/*
计数排序
因为最多出现n次 拿一个数组存 出现i次元素的有多少个
*/
    vector topKFrequent(vector& nums, int k) {
        unordered_mapcnt;//每个元素出现了多少次
        int n=nums.size();
         vectorans;
        vectorf(n+1);
        for(auto x:nums)cnt[x]++;

        for(auto [x,c]: cnt)f[c]++;

        int i=n;
        while(k>0)k-=f[i--];

        for(auto [x,c]:cnt)
        if(c>i)ans.push_back(x);
        
        return ans;
    }
};

061. 和最小的 k 个数对

class Solution {
    typedef vector VI;
    /*
多路归并
b0+a0  b0+a1 +... + a[n-1]
b1
.
.
.
b[m-1]

优先队列 存vector  不是int
    */
public:

    vector> kSmallestPairs(vector& a, vector& b, int k) {
        priority_queue,greater>heap;
         vectorans;
         int n=a.size(),m=b.size();
         for(int i=0;i