面试题简述

假设你现在有10亿个整数，请你找出其中最大的K个数，你会怎么做？如果数据量太大内存放不下，又该怎么办？

面试官想听的

1、是否能从算法的角度理清思路；

2、是否能从工程角度考虑落地实现；

3、是否能说清楚时间复杂度和空间复杂度。

面试示例回答

这个问题我会分两种情况考虑：

1、第一种情况，即如果内存能放得下；

2、第二种情况，即内存放不下

详细内容可跳转该链接查看详情：http://xhslink.com/o/5PabX17k4lE

由浅入深分析

1、算法核心思想

（1）使用最小堆保存当前排序后的前 K 个元素；

（2）新元素进来时与堆顶比较，若更大则替换，

2、为什么不用排序？主要从复杂度考虑

（1）排序的复杂度O（NlogN），不划算；

（2）堆的方式只需O（NLogK），很划算；

3、为什么是最小堆，不用最大堆？

（1）最小堆能在保持堆大小为K的前提下，随时淘汰当前K个数中最小的那个，从而在O（NlogK）的复杂度下求解最大的K个数。

（2）如果用最大堆反过来做，会保留 N - K 个没用的数据，空间和时间都会浪费很多。

4、外部排序的核心思想：

（1）把大数据拆成能放进内存的小块；

（2）各块内部排序；

（3）再用多路归并得到最终结果。

面试加分点

1、能清晰区分内存足够和内存不足两种场景；

2、能说清除为什么用最小堆而不是最大堆；

3、能写出时间复杂度。