堆的OJ题

703. 数据流中的第 K 大元素

题目链接：703. 数据流中的第 K 大元素

题目描述：

设计一个找到数据流中第 k 大元素的类（class）。注意是排序后的第 k 大元素，不是第 k 个不同的元素。

请实现 KthLargest 类：

• KthLargest(int k, int[] nums) 使用整数 k 和整数流 nums 初始化对象。
• int add(int val) 将 val 插入数据流 nums 后，返回当前数据流中第 k 大的元素。

示例：

输入：
["KthLargest", "add", "add", "add", "add", "add"]
[[3, [4, 5, 8, 2]], [3], [5], [10], [9], [4]]
输出：
[null, 4, 5, 5, 8, 8]

解释：
KthLargest kthLargest = new KthLargest(3, [4, 5, 8, 2]);
kthLargest.add(3);   // return 4
kthLargest.add(5);   // return 5
kthLargest.add(10);  // return 5
kthLargest.add(9);   // return 8
kthLargest.add(4);   // return 8

提示：

• 1 <= k <= 104
• 0 <= nums.length <= 104
• -104 <= nums[i] <= 104
• -104 <= val <= 104
• 最多调用 add 方法 104 次
• 题目数据保证，在查找第 k 大元素时，数组中至少有 k 个元素

解题思路： 这一题是典型的topK问题，第K大我们可以建小堆。第K小我们可以建大堆。为什么要这样呢？因为建小堆的话，我们的堆顶就是最小的。我Top一个后，新的堆顶就是倒数第二小的。当我们的堆只有的元素只有K个的时候。那么堆顶的元素就是 nums.size - k小的。反过来就是第K大的。nums这里指的是整个数组。

假设整个数组的大小为 7 ， k 为6。 那么当堆的大小为6时，堆顶的元素就是 nums.size - 1(nums.size - heap.size)。也就是第6大的数。所以，TOPK问题找第K大建小堆，找第K小建大堆，我们要反着来。虽然正着来也可以解决单纯的topK问题，但是这一题是有add操作的，如果正着来。那么前面pop掉最大的数据就丢失了。而最小的数据却没有关系，因为小堆存的是最大的K个数。堆顶是最大K个数中最小的一个。

所以这一题我们可以建一个小堆。然后把nums所有的数push进去，最后再把堆pop到K的大小。而每次add就push一次，再pop一次，即可维持堆的大小为K。

代码：

class KthLargest {
public:
    priority_queue<int,vector<int>,greater<int>> _min_heap;
    int _k;
    KthLargest(int k, vector<int>& nums) {
        _k = k ;
        for(auto& n : nums)
            _min_heap.push(n); 
        while(_min_heap.size() > k) _min_heap.pop();
    }
    
    int add(int val) {
        _min_heap.push(val);
        if(_min_heap.size() > _k) _min_heap.pop();
        return _min_heap.top();
    }
};

运行结果：

692. 前K个高频单词

题目链接： 692. 前K个高频单词

题目描述：

给定一个单词列表 words 和一个整数 k ，返回前 k 个出现次数最多的单词。

返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率， 按字典顺序 排序。

示例 1：

输入: words = ["i", "love", "leetcode", "i", "love", "coding"], k = 2
输出: ["i", "love"]
解析: "i" 和 "love" 为出现次数最多的两个单词，均为2次。
    注意，按字母顺序 "i" 在 "love" 之前。

示例 2：

输入: ["the", "day", "is", "sunny", "the", "the", "the", "sunny", "is", "is"], k = 4
输出: ["the", "is", "sunny", "day"]
解析: "the", "is", "sunny" 和 "day" 是出现次数最多的四个单词，
    出现次数依次为 4, 3, 2 和 1 次。

注意：

• 1 <= words.length <= 500
• 1 <= words[i] <= 10
• words[i] 由小写英文字母组成。
• k 的取值范围是 [1, **不同** words[i] 的数量]

**进阶：**尝试以 O(n log k) 时间复杂度和 O(n) 空间复杂度解决。

解题思路：

首先这一题有2个关键点，第一点是按频次比较。第二点是频次相同时，按字母序排序。所以这里我们要一个哈希表来统治所有字符串出现的次数。然后再把哈希表的这一对key，value值入堆，而堆的大小也和上题一样设置为K个。因为频次取前K个，所以我们对频次用小根堆排。但是频次相同的字符串又要按字母序排，所以对字母序排序我们又要用大堆。

比如第一个用例。我们用堆排好序是这样的。频次用小根堆排，而频次相同，我们则按大根堆对string排。

而因为我们的K为2，所以堆的大小只能是2。最后变成这样。

而此时我TOP得到的是字母序较大的值，所以我们在把堆的值填入返回的string数组时需要倒着填，因为小的要放在前面。

要实现这种排序，我们需要自己写一个cmp函数，作为priority_queue的第三个模板参数。

代码：

class Solution {
    typedef pair<string,int> PSI; 

    //排序的仿函数
    struct cmp
    {
        bool operator()(const PSI& a ,const PSI& b)
        {
            if(a.second == b.second)
            {
                //频次相同，用大根堆排
                return a.first < b.first;  //小的放下面
            }
            return a.second > b.second; //小根堆排，大的放下面
        }
    };

public:
    vector<string> topKFrequent(vector<string>& words, int k) {
        unordered_map<string,int> map; 
        //1.统计所有字符出现次数
        for(auto& word : words) map[word]++; 

        //2.将哈希表所有元素入堆
        priority_queue<PSI,vector<PSI>,cmp> heap; 
        for(auto& it : map) heap.push({it.first,it.second}); 
        //堆的大小只能为k 
        while(heap.size() > k) heap.pop(); 

        //将堆的元素逆序放到ret数组中
        vector<string> ret(k); 
        for(int i = k - 1; i >= 0 ; i--)
        {
            //将堆顶字符串放在数组的尾部，逆序放
            ret[i] = heap.top().first;
            heap.pop();
        }
        return ret;
    }
};

运行结果：

295. 数据流的中位数

题目链接：[295. 数据流的中位数

题目描述：

中位数是有序整数列表中的中间值。如果列表的大小是偶数，则没有中间值，中位数是两个中间值的平均值。

• 例如 arr = [2,3,4] 的中位数是 3 。
• 例如 arr = [2,3] 的中位数是 (2 + 3) / 2 = 2.5 。

实现 MedianFinder 类:

• MedianFinder() 初始化 MedianFinder 对象。
• void addNum(int num) 将数据流中的整数 num 添加到数据结构中。
• double findMedian() 返回到目前为止所有元素的中位数。与实际答案相差 10-5 以内的答案将被接受。

示例 1：

输入
["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"]
[[], [1], [2], [], [3], []]
输出
[null, null, null, 1.5, null, 2.0]

解释
MedianFinder medianFinder = new MedianFinder();
medianFinder.addNum(1);    // arr = [1]
medianFinder.addNum(2);    // arr = [1, 2]
medianFinder.findMedian(); // 返回 1.5 ((1 + 2) / 2)
medianFinder.addNum(3);    // arr[1, 2, 3]
medianFinder.findMedian(); // return 2.0

提示:

• -105 <= num <= 105
• 在调用 findMedian 之前，数据结构中至少有一个元素
• 最多 5 * 104 次调用 addNum 和 findMedian

解题思路：

题目是找中位数，那么我们可以用2个堆。一个大堆，一个小端。大于中位数的值放小堆里面，小于等于中位数的值放大堆里面。我们只需要保证两个堆的大小相等，或者大堆的大小比小堆大1。每当一次add操作时，我们先判断两个堆大小是否相等。如果相等，则说明要往大堆push数据，那么我们先把num放进小堆，再取小堆的堆顶放入大堆，这样大堆的长度就+1了。如果不相等，说明大堆的大小比小堆大1，那么我们要往小堆push数据，所以我们先把num放进大堆，再取大堆的堆顶放入小堆。

代码：

class MedianFinder {
public:
    priority_queue<int,vector<int>,greater<int>> _less_heap;//小堆
    priority_queue<int,vector<int>,less<int>> _greater_heap;//大堆

    MedianFinder() {

    }
    
    void addNum(int num) {
        if(_greater_heap.size() == 0)
        {
            //第一次插入，直接入大堆
            _greater_heap.push(num); 
            return; 
        }
        //其他次插入，判断俩个堆的大小
        if(_greater_heap.size() == _less_heap.size())
        {
            //两个堆的大小相等，则放进大堆，不过需要先把num放进小堆，取小堆的堆顶放入大堆
            _less_heap.push(num);
            int top = _less_heap.top();
            _less_heap.pop();
            _greater_heap.push(top); 
        }else 
        {
            //两个堆大小不相等，则说明大堆多一个，把num放进大堆，取大堆的堆顶放入小堆，俩个堆的大小则平衡
            _greater_heap.push(num); 
            int top = _greater_heap.top();
            _greater_heap.pop();
            _less_heap.push(top);
        }
    }
    
    double findMedian() {
        //如果俩个堆大小相等，返回堆顶和 /2 ，反之返回大堆堆顶
        if(_less_heap.size() == _greater_heap.size())
            return (_less_heap.top() + _greater_heap.top()) / 2.0; 
        return _greater_heap.top();
    }
};

运行结果：