面试题:最小的k个数题目：输入n个整数，找出其中

参考答案:

正确答案：

这道题最简单的思路莫过于把输入的n个整数排序，排序之后位于最前面的k个数就是最小的k个数。这种思路的时间复杂度是O(n/ogrt)，面试官会提示我们还有更快的算法。
◆解法一：O(n)的算法，只有当我们可以修改输入的数组时可用
从解决面试题29“数组中出现次数超过一半的数字”得到了启发，我们同样可以基于Partition函数来解决这个问题。如果基于数组的第k个数字来调整，使得比第k个数字小的所有数字都位于数组的左边，比第k个数字大的所有数字都位于数组的右边。这样调整之后