☆* o(≧▽≦)o *☆嗨~我是小奥🍹
📄📄📄个人博客：小奥的博客
📄📄📄CSDN：个人CSDN
📙📙📙Github：传送门
📅📅📅面经分享（牛客主页）：传送门
🍹文章作者技术和水平有限，如果文中出现错误，希望大家多多指正！
📜 如果觉得内容还不错，欢迎点赞收藏关注哟！ ??
Top K问题模板
10亿个数中如何高效地找到最大的一个数
分而治之：将10亿个数据分成1000份，每份100万个数据，找到每份数据中最大的那个数据，最后在剩下的1000个数据里面找出最大的数据。 从100万个数据遍历选择最大的数，此方法需要每次的内存空间为10^6*4=4MB，一共需要1000次这样的比较。
10亿个数中如何高效地找到最大的第 K 个数
对于top K类问题，通常比较好的方案是分治+hash+小顶堆：
- 先将数据集按照Hash方法分解成多个小数据集
- 然后用小顶堆求出每个数据集中最大的K个数
- 最后在所有top K中求出最终的top K。
Top K常用的方法
- 快排+选择排序：排序后的集合中进行查找
- 时间复杂度： 时间复杂度为O(NlogN)
- 缺点：需要比较大的内存，且效率低
- 局部淘汰：取前K个元素并排序，然后依次扫描剩余的元素，插入到排好序的序列中(二分查找)，并淘汰最小值。
- 时间复杂度： 时间复杂度为O(NlogK) (logK为二分查找的复杂度)。
- 分治法：将10亿个数据分成1000份，每份100万个数据，找到每份数据中最大的K个，最后在剩下的1000*K个数据里面找出最大的K个，100万个数据里面查找最大的K个数据可以使用Partition的方法
- Hash法： 如果这10亿个数里面有很多重复的数，先通过Hash法，把这10亿个数字去重复，这样如果重复率很高的话，会减少很大的内存用量，从而缩小运算空间，然后通过分治法或最小堆法查找最大的K个数。
- 小顶堆： 首先读入前K个数来创建大小为K的小顶堆，建堆的时间复杂度为O(K)，然后遍历后续的数字，并于堆顶（最小）数字进行比较。如果比最小的数小，则继续读取后续数字；如果比堆顶数字大，则替换堆顶元素并重新调整堆为最小堆。
- Trie树： 如果是从10亿个重复比较多的单词找高频词汇，数据集按照Hash方法分解成多个小数据集，然后使用Trie树统计每个小数据集中的query词频，之后用小顶堆求出每个数据集中出现频率最高的前K个数，最后在所有top K中求出最终的top K。
- 适用范围：数据量大，重复多，但是数据种类小可以放入内存
- 时间复杂度：O(Len*N)，N为字符串的个数，Len为字符串长度
- 桶排序：一个数据表分割成许多buckets，然后每个bucket各自排序，或用不同的排序算法，或者递归的使用bucket sort算法。也是典型的divide-and-conquer分而治之的策略。
- 使用范围：如果已知了数据的范围，那么可以划分合适大小的桶，直接借用桶排序的思路
- 时间复杂度：O(N*logM)，N 为待排序的元素的个数，M为桶的个数
- 计数排序：计数排序其实是桶排序的一种特殊情况。当要排序的 n 个数据，所处的范围并不大的时候，比如最大值是 k，我们就可以把数据划分成 k 个桶。每个桶内的数据值都是相同的，省掉了桶内排序的时间。
- 适用范围：只能用在数据范围不大的场景
- 时间复杂度：O(N)
- 基数排序：将整数按位数切割成不同的数字，然后按每个位数分别比较。
- 适用范围：可以对字符串类型的关键字进行排序。
- 时间复杂度： O(N*M)，M为要排序的数据的位数