【优先级队列】前K个高频单词 && 数据流的中位数

692. 前K个高频单词

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

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

示例 1：

代码语言：javascript代码运行次数：0运行复制

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

示例 2：

代码语言：javascript代码运行次数：0运行复制

输入: ["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) 空间复杂度解决。

解题思路：哈希表 + 优先级队列

这道题很明显还是要使用 topk 问题的处理方式来解决，也就是使用堆来解决，只不过这道题稍微要多处理其它的内容！

首先因为需要按单词出现频率由高到低排序，那么就需要统计单词的出现频率，就可以 使用哈希表来统计！

然后将哈希表内容按 topk 模式进行处理，这里有细节，就是因为我们既要获得堆中的字符串，又得根据频次来维护堆，所以优先级队列存放的是一个键值对 pair<string, int>，还有就是因为==频次从高到小排序，那么我们就要建立一个小根堆==，所以要自己写一个比较器 compare，这里用仿函数为例！

在比较器中还要特别注意一个细节，我们需要特殊判断一下次数相等的情况，此时要根据字典顺序从低到高排序，所以 对于字典序列要搞个大堆才行，和频次是相反的，一定要弄清楚比较器中大于和小于的区别，大于表示的是建小堆，小于表示的是建大堆，别搞错了！

接着就是一个循环，先将哈希表中的键值对插入，然后判断一下优先级队列是否超过了 k 个元素，是的话直接让堆顶 pop 掉即可，因为我们建立的堆是与序列相反的，那么 pop 的就是不满足要求的！以此类推，直到哈希表遍历完毕！

最后就是将堆中元素取出，然后放到数组中返回，注意因为堆中次序和返回的次序是相反的，所以我们要先逆序，再返回结果！

代码语言：javascript代码运行次数：0运行复制

struct compare
{
    bool operator()(pair<string, int>& p1, pair<string, int>& p2)
    {
        // 特殊判断一下次数相等的情况
        if(p1.second == p2.second)
            return p1.first < p2.first; // 注意细节，字典顺序是从低到高，所以字典要搞个大堆才行，和频次相反
        return p1.second > p2.second;
    }
};

class Solution {
public:
    vector<string> topKFrequent(vector<string>& words, int k) {
        // 先统计每个单词出现次数
        unordered_map<string, int> hash;
        for(auto& word : words)
            hash[word]++;

        // 将哈希表内容按topk模式进行处理，使用小根堆
        priority_queue<pair<string, int>, vector<pair<string, int>>, compare> heap;
        for(auto& e: hash)
        {
            heap.push(e);

            if(heap.size() > k)
                heap.pop();
        }

        // 将堆中元素取出
        vector<string> str;
        while(!heap.empty())
        {
            str.push_back(heap.top().first);
            heap.pop();
        }

        reverse(str.begin(), str.end()); // 别忘了最后是从大到小排序，所以要逆序一下
        return str;
    }
};

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：

代码语言：javascript代码运行次数：0运行复制

输入
["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

解题思路一：直接排序（超时）

这种思路比较简单，就是直接在 addNum() 函数中，将 num 插入到数组后直接调用 sort() 函数对数组进行排序，然后在 findMedian() 中就能直接通过索引来得到平均值或者中值！

在处理的时候时间复杂度为 O(nlogn)，在查找中位数的时候时间复杂度为 O(1)，但是在这道题中处理的时候是会超时的，所以不考虑这种方式！

解题思路二：插入排序（超时）

因为每次我们在 addNum() 的时候，其实就只插入了一个元素，那我们可以考虑使用插入排序，因为我们可以让原数组保持有序的情况，只需要处理一个新元素的排序即可，而不需要像解法一中每次调用 addNum() 的时候都需要重新去排序！

那么使用插入排序的时间复杂度对于一个元素来说，是 O(n)，相比解法一有了提升，然后在查找中位数的时候时间复杂度依然是 O(1)，但这道题在处理插入的时候，也耐不住大量极端的数据，所以也是会超时的！

科技改变生活-雨落星辰 - 所有的伟大,都源于一个勇敢的开始

【优先级队列】前K个高频单词 && 数据流的中位数