【大数据开发工程师】面试——海量数据处理 之 Top K问题

问题示例：

从十亿个正整数中找出指定的数字。或者排序。

思路

先去重

1. 直接排序。然后在排序后的集合上进行查找，取出前K位。

问题是：int - 32位 - 8个字节，10亿个数*8字节得 4G存储空间。现在大部分机器内存都在8G以上，服务器内存都在128G，这个思路也能做排序。

   但是我们的目标是找出前K位，但是这种方式把所有的数的排序了，做了很多无用功。

2.用容器保存K个数。将剩余的数与容器中的最小数字比较，如果后续的数字都小于这个最小值，则容器中的K个数即是我们想要的TOP K。

3.把十亿数字分成1000份。每份100万个数据，然后找到每份的前K个，最后在1000*K里面找出最大的前K个。