10 亿个数中找出最大的 10000 个数（top K 问题）

1. 对全部数据直接进行排序

• 时间复杂度 O(nlogn)
• 空间复杂度 O(n)

将 10 亿数据直接进行快排，然后如果大堆长度大于 10000，继续将大堆进行快排。 如果小于 10000 ，那么将最近一次的小堆再次进行快排。如果这个大堆长度加上之前的长度大于 10000，那么对这个大堆进行完整的快排。并取最大的 n 个数。

2.局部淘汰法

• 时间复杂度 O(n+m^2) m 为当前容器大小 10000
• 空间复杂度 O(m)

先保存 10000 个数，然后将后续的数依次与 10000 里最小的数比较，小的直接丢弃，大的进行替换。最后这 10000 个数就是答案。

3.分治法

• 时间复杂度 O(nlogn)
• 空间复杂度 O(max(a,b)) a 为每份的长度 这里为 100 万，b 为最后的 m 份的最大 k 这里为 100 份的最大 10000 即 100 万。

先将 1 亿个数分成 100 份， 每份 100 万个数。然后对每一份进行快排找出最大的 10000 个数。
方法是：快排中如果大堆大于 10000 ，继续对大堆进行快排。如果小于 10000，那么对最近的小堆进行快排，如果大堆长度 + 之前的大堆长度满足。那么对大堆进行完全快排取最大的 n 个数。
这样找出了 100 份 最大的 10000 个数。继续上边的思路进行快排直到找出最大的 10000 个数。

4.Hash 法

先将所有的数存入 hash 表中去重复，减少数据量。然后分治法。

https://blog.csdn.net/zyq522376829/article/details/47686867