The 20th day of the special assault version of the sword offer

剑指 Offer II 059. 数据流的第 K 大数值

小顶堆

• 第kBig is equivalent to,The penultimate after the sequence is ascendingk个数.
• 容易发现,倒数第kThe previous numbers are no longer available,Then we can throw away the useless ones,Then keep the sequence in order after insertion.
• 由于这里add会操作 $10^4$ 次,So it needs less time complexity,It is easy to think of using a heap structure（大小保持为<= $k$ ）,或者multiset.

class KthLargest {
    
public:
    int k = 0;
    priority_queue<int,vector<int>,greater<int>> heap;
    KthLargest(int k, vector<int>& nums) {
    
        for(int num: nums) heap.push(num);
        this->k = k;
    }
    
    int add(int val) {
    
        heap.push(val);
        while(heap.size() > k) heap.pop();
        return heap.top();
    }
};

---

剑指 Offer II 060. 出现频率最高的 k 个数字

方法一、Use the hash table to record the number of times,Then traverse the hash table to let the heap be maintained before $k$ 大,时间复杂度就为$O(Nlogk)$ .

class Solution {
    
public:
    typedef pair<int,int> PII;
    unordered_map<int,int> cnts;
    static bool cmp(const PII &a, const PII &b) {
    
        return a.second > b.second;
    }
    vector<int> topKFrequent(vector<int>& nums, int k) {
    
        for(int num: nums) {
    
            cnts[num]++;
        }
        //自定义排序规则
        priority_queue<PII,vector<PII>,decltype(&cmp)> heap(cmp);
        for(auto p: cnts) {
    
            if(heap.size() == k) {
     //Keep the heap size no larger than k
                if(heap.top().second < p.second) {
    
                    heap.pop();
                    heap.emplace(p);
                }
            } else heap.emplace(p);
        }
        vector<int> res;
        while(heap.size()) {
    
            res.emplace_back(heap.top().first);
            heap.pop();
        }
        return res;
    }
};

方法二、Use the hash table to record the number of times,Then sort out before taking outk大的数即可.时间$O(NlogN)$

class Solution {
    
public:
    unordered_map<int,int> cnts;
    static bool cmp(const pair<int,int> &a, const pair<int,int> &b) {
    
        return a.second > b.second;
    }
    vector<int> topKFrequent(vector<int>& nums, int k) {
    
        int maxx = 0;
        for(int num: nums) {
    
            cnts[num]++;
        }
        vector<pair<int,int>> ls;
        for(auto p: cnts) {
    
            ls.emplace_back(p);
        }
        sort(ls.begin(),ls.end(),cmp);
        ls.erase(ls.begin()+k,ls.end());
        vector<int> res;
        for(auto num: ls) res.emplace_back(num.first);
        return res;
    }
};

---

剑指 Offer II 061. 和最小的 k 个数对

• It's easy to think of a way：Violent all pairs,然后排序取前 $k$ 小,时间复杂度是 $O(N^2)$ It will time out here.
• 仔细思考会发现,$nums1[0]+nums2[0]$ 一定是最小的,And then the next smallest must be one of them： $nums1[0]+nums2[1]$ 、 $nums1[1]+nums2[0]$ ,以此类推,This way we don't have to traverse all pairs, just use the rules to find the first few,Here, a small top heap is needed to maintain the relationship between pairs.

class Solution {
    
public:
    typedef pair<int,int> PII;
    vector<vector<int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) {
    
        auto cmp = [&nums1,&nums2](const PII &a, const PII &b) {
    
            return nums1[a.first]+nums2[a.second] > nums1[b.first]+nums2[b.second];
        };

        int n = nums1.size();
        int m = nums2.size();
        priority_queue<PII,vector<PII>,decltype(cmp)> heap(cmp);
        for(int i = 0; i < min(k,n); i++) {
    
            heap.emplace(i,0);
        }
        vector<vector<int>> res;
        while(k-- && heap.size()) {
    
            auto [x,y] = heap.top();
            heap.pop();
            res.push_back({
    nums1[x],nums2[y]});
            if(y+1 < m) heap.emplace(x,y+1);
        }
        return res;
    }
};

参考：https://leetcode.cn/problems/qn8gGX/solution/he-zui-xiao-de-k-ge-shu-dui-by-leetcode-eoce6/