文件搜索
10亿个数中如何高效地找到最大的一个数以及最大的第K个数
10亿个数中如何高效地找到最大的一个数
将10亿个数据分成1000份，每份100万个数据，找到每份数据中最大的那个数据，最后在剩下的1000个数据里面找出最大的数据。 从100万个数据遍历选择最大的数，此方法需要每次的内存空间为10^6*4=4MB，一共需要1000次这样的比较。
10亿个数中如何高效地找到第K个数
对于top K类问题，通常比较好的方案是分治+hash+小顶堆：
- 先将数据集按照Hash方法分解成多个小数据集
- 然后用小顶堆求出每个数据集中最大的K个数
- 最后在所有top K中求出最终的top K。
如果是top词频可以使用分治+ Trie树/hash +小顶堆：
- 先将数据集按照Hash方法分解成多个小数据集
- 然后使用Trie树或者Hash统计每个小数据集中的query词频
- 之后用小顶堆求出每个数据集中出频率最高的前K个数
- 最后在所有top K中求出最终的top K。
时间复杂度：建堆时间复杂度是O(K),算法的时间复杂度为O(NlogK)。