剑指offer专项突击版第20天

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

小顶堆

• 第k大就等同于，序列升序后倒数第k个数。
• 容易发现，倒数第k个之前的数都用不到了，那么我们可以扔掉那些没用的，然后保持插入后序列仍然有序即可。
• 由于这里add会操作 $10^4$ 次，所以需要较小的时间复杂度，容易想到使用堆结构（大小保持为<= $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();
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

---

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

方法一、使用哈希表记录次数，然后遍历哈希表让堆来维护前 $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) { //保持堆大小不大于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;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

方法二、使用哈希表记录次数，然后再排序取出前k大的数即可。时间$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;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

---

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

• 容易想到一个方法：暴力出所有数对，然后排序取前 $k$ 小，时间复杂度是 $O(N^2)$ 在这里会超时。
• 仔细思考会发现，$nums1[0]+nums2[0]$ 一定是最小的，然后接下第二小肯定是它们其中之一： $nums1[0]+nums2[1]$ 、 $nums1[1]+nums2[0]$ ，以此类推，这样我们就不用遍历出所有数对了只需利用规律找出前几个即可，这里需要用小顶堆来维护数对间的关系。

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;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

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