题目

题目来源：力扣（LeetCode）

设计一个算法，找出数组中最小的k个数。以任意顺序返回这k个数均可。
示例：

输入： arr = [1,3,5,7,2,4,6,8], k = 4
输出： [1,2,3,4]

解法一：排序

思路分析

一种比较简单的实现方式是，先对数组进行从小到大的排序，然后取出前 k 个数即可

  1. /**
  2.  * @param {number[]} arr
  3.  * @param {number} k
  4.  * @return {number[]}
  5.  */
  6. /**
  7.   对数组进行从小到大的排序后，取前 k 个数
  8. */
  9. var smallestK = function(arr, k) {
  10.   if (k >= arr.length) return arr;
  12.   arr.sort((a, b) => a -b);
  14.   let  res = [];
  15.   for (let i = 0; i < k; i++) {
  16.     res.push(arr[i])
  17.   }
  19.   return res
  20. };

解法二：最大堆

思路分析

堆分为 最大堆 和 最小堆，最大堆的堆顶元素是堆中最大的，最小堆的堆顶元素是堆中最小的。这里我们可以使用最大堆，实时维护数组的前 k 个数。

  1. 首先将前 k 个数插入大根堆中，然后从第 k + 1 个数开始遍历；
  2. 如果当前遍历到的数比大根堆的堆顶元素要小，就把堆顶的元素弹出，然后再把当前遍历到的元素加入到堆中
  3. 最后将大根堆里数返回即可
  1. /**
  2.  * @param {number[]} arr
  3.  * @param {number} k
  4.  * @return {number[]}
  5.  */
  7. // 交换堆中的元素，使堆的结构正常
  8. function build(heap, i = 0) {
  9.   let size = heap.length;
  10.   while (i < size) {
  11.     let temp = i;
  12.     let left = 2 * i + 1; // 二叉堆左侧子节点
  13.     let right = 2 * i + 2; // 二叉堆右侧子节点
  15.     // 如果元素 heap[temp] 比它的左侧子节点要小，交换元素和它的左侧子节点
  16.     if (left < size && heap[left] > heap[temp]) {
  17.       temp = left;
  18.     }
  20.     // 如果元素 heap[temp] 小于它的右侧子节点，交换元素和它的右侧子节点
  21.     if (right < size && heap[right] > heap[temp]) {
  22.       temp = right;
  23.     }
  25.     // 在找到最小子节点的位置后，校验它的值是否和 element 相同，不同，则进行交换
  26.     if (temp === i) break;
  27.     [heap[temp], heap[i]] = [heap[i], heap[temp]];
  28.     i = temp;
  29.   }
  30. }
  32. var smallestK = function(arr, k) {
  33.   if (k >= arr.length) return arr;
  34.   // 创建一个最大堆，在堆中放数组的前 k 个元素
  35.   let heap = arr.slice(0, k);
  36.   let i = k;
  37.   const size = arr.length;
  39.   // 对堆中的元素进行交换，使堆的结构正常
  40.   for (let i = Math.floor(k/2) - 1; i >= 0; i--) {
  41.     build(heap, i)
  42.   }
  44.   // 遍历数组中 k 后面的元素
  45.   // 如果当前元素比堆顶元素小，就把堆顶元素移除，然后再把当前元素放到堆中
  46.   while (i < size) {
  47.     if (arr[i] < heap[0]) {
  48.       heap[0] = arr[i]; // 将当前元素放到堆顶
  49.       build(heap); // 交互堆中元素，使堆结构正常
  50.     }
  51.     i++;
  52.   }
  54.   return heap
  56. };

解法三：快排

思路分析

我们知道快速排序可以通过一趟排序将要排序的数据分割成独立的两部分，小于等于分界值的元素都会被放到数组的左边，大于的元素都会被放到数组的右边，返回返回分界值的下标。与快速排序不同的是，快速排序会根据分界值的下标递归处理划分的两侧，而这里我们只处理划分的一边。

这道题的解题思路就是，每次确定分界值的位置(下标)之后，我们都要判断这个位置是否等于 k :

  • 如果等于 k ，那么它前面的 k 个元素都是小于分界值的，后面的元素都是大于分界值的，也就是说它前面的 k 个元素就是我们要找的；
  • 如果小于 k ，说明它前面的元素都是我们要找的，但是还不够，我们还要继续往后找剩下的；
  • 如果大于 k ，说明它前面的元素够 k 个了，我们只需要在它前面找即可
  1. /**
  2.  * @param {number[]} arr
  3.  * @param {number} k
  4.  * @return {number[]}
  5.  */
  7. var smallestK = function(arr, k) {
  8.   if (k >= arr.length) return arr;
  10.   const res = new Array(k);
  11.   quickSort(arr, res, k, 0, arr.length - 1);
  12.   return res;
  13. };
  15. /**
  16.  *@param {number[]} arr
  17.  *@param {number[]} res 
  18.  *@param {number} k
  19.  *@param {number} left 元素下标
  20.  *@param {number} right 元素下标
  21.  */
  22. function quickSort(arr, res, k, left, right) {
  23.   const start = left; // 数组中元素的下标
  24.   const end = right;  // 数组中元素的下标
  26.   while (left < right) {
  27.     while (left < right && arr[right] >= arr[start]) {
  28.       right--;
  29.     }
  31.     while (left < right && arr[left] <= arr[start]) {
  32.       left++
  33.     }
  35.     swap(arr, left, right)
  36.   }
  38.   swap(arr, left, start);
  40.   if (left > k) {
  41.     // 分界值的下标大于 k , 说明分界值前面的元素够 k 个了，在分界值前面找即可
  42.     quickSort(arr, res, k, start, left - 1)
  43.   } else if (left < k) {
  44.     // 分界值的下标小于 k , 说明分界值前面的元素都是我们要找的，但还不够，还要继续往后找
  45.     quickSort(arr, res, k, left + 1, end)
  46.   } else {
  47.     // 分界值的下标等于 k, 说明分界值前面的元素都是我们要找的元素，取前面 k 个元素即可
  48.     for (let i = 0; i < k; i++) {
  49.       res[i] = arr[i]
  50.     }
  51.   }
  52. }
  54. // 交换数组中的两个元素
  55. function swap(arr, i, j) {
  56.   if (i == j) return
  58.   [arr[i], arr[j]] = [arr[j], arr[i]]
  59. }