面试题40. 347. 692.| 前K个元素 LeetCode

  这是一道经常在面试中被问到的题目，要你设计一个算法，求一堆数中的前K个元素。正常的思路是先将数组排序，然后找到前K个元素，但这样做通常会面临时间复杂度、空间复杂度双双过高的问题。如果面试官问你，这堆数据有好几百G，甚至上T，你怎么办？

  所以，我们就得想其他办法来解决这个问题。一个思路是，利用哈希表的思想来解题，如计数排序等。还有一个思路是利用堆排序来解题，这是比较常用的方法。

  整体思路就是，先遍历整个数组，将满足要求的元素放入堆中，维持堆的大小为K；当遍历结束的时候，堆就是题目要求的前K个元素。

分析：

  求前K大元素用小根堆来解答，这题需要先用一个哈希表来计算每个元素的频率，然后再用小根堆来求频率最高的前K个元素。

  需要注意的是，c++的优先队列容器默认是大根堆。

分析：

  这题的关键点在于当出现的频率相同时，需要按照字母顺序排序，最简单的做法是按照老方法：

1. 先用哈希表计算单词频率

2. 再用小根堆存储前K高频单词，并同时判断频率是否相等，来安排单词顺序

3. 将小根堆存储到数组中

  这里需要用到c++的operator方法，来重载优先队列容器，使小根堆在存储元素的同时，也比较单词的字母大小。注意小根堆最后输出的时候要翻转数组。