题目：输入n个整数，找出其中最小的k个数。例如输入{4,5,1,6,2,7,3,8}这8个数字，则最小的4个数字是1,2,3,4。

分析

这道题目跟上一道：面试题29：数组中出现次数超过一半的数字 类似，都是通过Partition()的思路来解题。通过Partition()获得index，判断index==k，如果等于k，那么表明在index左边的k个数都小于index所指向的数，并且也小于index右边的数。那么就找出了本题所要求的最小的k个数。如果index>k，则第k小的数在[start,index-1]之间，如果index<k，则第k小的数在[index+1,end]之间。知道最后求得index==k，退出循环。然后输出[0,k)之间的数，就是最小的k个数。

代码实例

View Code

海量数据处理下的处理方法

如果要处理的数据量非常大，那么对进行排序就不切实际，我们可以通过大根堆这样的数据结构来求最小的k个数。

创建一个大小为k的大根堆，遍历数据文件，如果大根堆不满，则往大根堆中插入数；如果大根堆满，则比较堆顶的数与读取到的数，如果读取到的数小于堆顶的数，那么删除堆顶的数，并插入刚扫描的数。采用这样的方法扫描全部数据。时间复杂度为O(nlog(k))

本文转自xwdreamer博客园博客，原文链接：http://www.cnblogs.com/xwdreamer/archive/2012/05/08/2489733.html，如需转载请自行联系原作者