剑指 Offer II 堆

059. 数据流的第 K 大数值

class KthLargest {

public:

priority_queue<int,vector<int>,greater<int>>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<int>& 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<int> topKFrequent(vector<int>& nums, int k) {

        unordered_map<int,int>cnt;//每个元素出现了多少次

        int n=nums.size();

         vector<int>ans;

        vector<int>f(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<int> VI;

    /*

多路归并

b0+a0  b0+a1 +... + a[n-1]

b1

.

.

.

b[m-1]

优先队列 存vector<int>  不是int

    */

public:

    vector<vector<int>> kSmallestPairs(vector<int>& a, vector<int>& b, int k) {

        priority_queue<VI,vector<VI>,greater<VI>>heap;

         vector<VI>ans;

         int n=a.size(),m=b.size();

         for(int i=0;i<m;i++)heap.push({b[i]+a[0],0,i});

         // b[i]+a[0]用于比较

         //0是a下标 i是b下标 用于传答案 

         while(heap.size()&&k)

         {

             k--;

             VI t=heap.top();

             heap.pop();

             ans.push_back({a[t[1]],b[t[2]]});

             if(t[1]+1<n)heap.push({a[t[1]+1]+b[t[2]],t[1]+1,t[2]});

         }

        return ans;

    }

};

巴特西

剑指 Offer II 堆

059. 数据流的第 K 大数值

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

061. 和最小的 k 个数对

最新文章

热门文章