海量数据求top K问题

问题：海量数据求top K问题

• https://blog.csdn.net/zyq522376829/article/details/47686867
• 10亿个数中找出最大的10000个数

方式1：排序(快排)

• 时间复杂度：O(NlogN)
• 空间复杂度：O(NlogN)

方式2：局部淘汰

• 1、定义一个数组存储最大10000个数
• 2、遍历10亿数，与最大数数组的最小数对比，大于则加入最大数数组
• 时间复杂度：O(N + (M*N))
• 空间复杂度：O(1)

方式3：归并（分治）

• 1、10亿数据分成若干份
• 2、找出每一个份的前10000个数，得100万个数
• 3、对100万个数划分为二，分治
• 时间复杂度：常数

方式4：最小堆

• 1、10000个数建最小堆
• 2、遍历剩下的数，和堆顶对比，比堆顶大则替换，重新建堆
• 时间复杂度：O(Nmlogm)
• 空间复杂度：堆原地排序，O(1)