最小的K个数

《剑指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;
}