题目描述
- 输入n个整数，找出其中最小的K个数。
- 例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4。
解法1
- 对数组排序，取前边k个数存到list集合中
- 该解法时间复杂度依赖于排序
代码实现
解法2
- 基于partition函数
- 只有当我们可以修改输入的数组时可用
代码实现
解法3
- 适合海量数据的处理
- 创建一个用于保存最小k个数的容器
- 第一步是放入k个元素，
- 第二步是比较容器中最大的数与当前数组遍历的那个数的大小
- 如果容器中最大的数比当前遍历的数大，就移除该数，并放入当前遍历的那个数
- 最大堆或红黑树都能实现这样的容器
