题目：输入n个整数，找出其中最小的k个数。例如输入4、5、1、6、2、7、3、8，则最小的4个数字是1、2、3、4。
该题的解答思路是把输入的n个整数排序，这样排在最前面的k个数就是最小的k个数。只是这种思路的时间复杂度为O(nlogn)，还有更快的解决思路。
问题解法一：基于Random-Partition的思想
在【面试题】数组中出现次数超过一半的数字中已经用到过这种思路，还是基于Partition()函数来解决这个问题。
解题思想：受快排算法的启发，先在数组中随机选择一个数字，然后调整数组中数字的排序，使得比选中数字小的都排在它左边，比选中数字大的都排在它的右边。如果这个选中的数字的下标刚好是k，则此时数组中位于k左边的数字就是最小的k个数，问题得解。否则，如果排序后它的下标大于k，则继续在它的左边找。如果下标小于k，则继续在它的右边找。这种算法的时间复杂度是O(n)。
c++参考代码实例：
// random quick select, finish when index is k,
// time complexity is O(n), no auxiliary space usage
void GetLeastNumbers_Solution1(int* input, int n, int* output, int k)
{
if (input == NULL || output == NULL || k > n || n <= 0 || k <= 0)
return;
int start = 0;
int end = n – 1;
int index = Partition(input, n, start, end);
while (index != k – 1)
{
if (index > k – 1)
{
end = index – 1;
index = Partition(input, n, start, end);
}
else
{
start = index + 1;
index = Partition(input, n, start, end);
}
}
for(int i = 0; i < k; ++i)
output[i] = input[i];
}
关于Partition函数及其理解，参考【面试题】数组中出现次数超过一半的数字。
注意：这种思路会修改输入的数组，因为Random-Partition是要交换数组中的数字的。另外，输入的n个数字要全部读入内存。如果n很大，数据是存在硬盘等设备中不能一次读入的时候，这个方法就不管用了。
解法二：O(nlogk)的算法，适合处理海量数据
创建一个大小为k的容器来存储最小的k个数字。每次读入一个数字x，如果容器未满，则直接把x放入容器之中；如果容器已满，则找出容器中最大的数字m，如果x小于m，则用x替换m，否则抛弃x。
总结一下所有可能的容器操作就是：（1）找到k个数字中的最大值；（2）删除最大数；（3）插入一个新数字。可以用二叉树来实现这个容器，这3个操作可以在O(logk)时间内完成。所以总的时间复杂度就是O(nlogk)。
可以用不同的二叉树来实现这个容器，比如最大堆(也称大顶堆)。在最大堆中，根节点的值总是大于它的子树中任意结点的值。所以可以在O(1)的时间内找到容器中的最大值，但删除和插入还是要O(logk)的时间。
从头实现一个最大堆需要一定的代码，在面试的短时间内很难完成。还可以采用红黑树(一种平衡二叉树)来实现这个容器。在红黑树中查找、删除和插入操作都是O(logk)时间。STL中的set和multiset都是基于红黑树实现的，如果面试官允许的话，可以直接拿来用。
参考代码：
typedef multiset<int, greater<int> > intSet;
typedef multiset<int, greater<int> >::iterator setIterator;
void GetLeastNumbers_Solution2(const vector<int>& data,
intSet& leastNumbers,
int k)
{
leastNumbers.clear();
if (k < 1 || data.size() < k)
return;
vector<int>::const_iterator iter = data.begin();
for (; iter != data.end(); ++ iter)
{
if((leastNumbers.size()) < k)
leastNumbers.insert(*iter);
else
{
setIterator iterGreatest = leastNumbers.begin();
if(*iter < *(leastNumbers.begin()))
{
leastNumbers.erase(iterGreatest);
leastNumbers.insert(*iter);
}
}
}
}
注：参考代码中的data.end()也可以先保存起来，不必每次都求一次值。
这种解法适合海量数据的输入，不必把这些海量数据一次性全部载入内存(由于内存受限，也无法做到)。
《剑指Offer》读书笔记