《剑指offer》刷题笔记。如有更好解法，欢迎留言。
关键字：数组 高级排序 堆
题目描述：
输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。
思路：
- 可以使用堆排序或者快速排序。
-
我这里维护一个最小堆
初始化
堆为空，直接进入
堆还为未满，根据大小关系添加到上面或下面
添加到底部
添加到顶部
堆已满，而且顶部最大，将顶部移除再添加
重排堆，保证上面最大
比堆顶都大的元素直接跳过
同理，替换堆顶
重排堆
遍历完成，输出堆 - 完整代码
function GetLeastNumbers_Solution(input, k)
{
if(input.length === k){
return input.sort();
}else if(input.length < k){
return [];
}
if(k === 0){
return [];
}
let arr = [];
for(let i = 0;i < input.length;i++){
if(arr.length === 0){
arr.push(input[i]);
}else if(arr.length < k){
if(input[i] > arr[arr.length-1]){
arr.push(input[i]);
}else{
arr.unshift(input[i]);
}
}else if(arr.length === k){
if(input[i] < arr[arr.length-1]){
arr.pop();
arr.push(input[i]);
}
arr.sort();
}
}
return arr;
}
