[链接](https://blog.csdn.net/qq_40816360/article/details/95374485) 输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4。 * [3、最大堆O(nlogk)](https://blog.csdn.net/daaikuaichuan/article/details/85239149#font_size43Onlogkfont_54) * [4、基于快排的算法O(n)](https://blog.csdn.net/daaikuaichuan/article/details/85239149#font_size44Onfont_100) 思路 - partition思想，不断地分割数组，partition前面的都是小于partition的，后面的都是大于partition的，那么只要partition的下标为k-1，那么前面的数据就是最小的K个数； - 堆方法（面试官倾向的方法，适合海量数据），维护容量为K的大顶堆，先对前k个数创建大顶堆，然后从第k+1个数开始，看是否比堆顶小，是的话就将这个数和堆顶交换，并从新调整为大顶堆 ； ``` function GetLeastNumbers_Solution(input, k) { // write code here if (k > input.length || !k || !input || input.length === 0) { return [] } let index = partition(input, 0, input.length - 1) while (index !== k-1) { if (index < k-1){ index = partition(input, index + 1, k-1) } else { index = partition(input, k-1, index - 1) } } return input.slice(0, index + 1).sort() } function partition(arr, low, high) { var pivot = arr[low] while (low <= high) { while (low <= high && arr[high] >= pivot) { high-- } [arr[low], arr[high]] = [arr[high], arr[low]] while (low <= high && arr[low] < pivot) { low++ } [arr[low], arr[high]] = [arr[high], arr[low]] } return low } ``` ``` // 堆方法 function GetLeastNumbers_Solution(input, k) { // write code here if (k > input.length || !k || !input || input.length === 0) { return [] } let heap = input.slice(0, k) makeMaxHeap(heap) for (let i = k; i < input.length; i++) { if (input[i] < heap[0]) { heap[0] = input[i] heapAdjust(heap, 0, k) } } return heap.sort() } function makeMaxHeap(arr) { let startIndex = Math.floor(arr.length / 2) for (let i = startIndex; i >= 0; i--){ heapAdjust(arr, i, arr.length) } } function heapAdjust(arr, s, m) { let temp = arr[s] for (let i = s * 2 + 1; i < m; i = i * 2 + 1) { if (i + 1 < m && arr[i] < arr[i + 1]) { i++ } if (temp > arr[i]) { break } else { arr[s] = arr[i] s = i } arr[s] = temp } } ```