最小的k个数 - 大师兄

1. 题目描述

输入 n 个整数，找出其中最小的 k 个数。例如输入 4、5、1、6、2、7、3、8 这 8 个数字，则最小的 4 个数字是 1、2、3、4。

2. 思路分析

利用“快速排序”的中的 partition 操作：返回 index，小于 index 对应元素的元素都放在了左边，大于 index 对应元素的元素都放在右边。

利用这个特性，只要我们的 partition 返回值是 k - 1，那么数组中前 k 个元素已经被摆放到了正确位置，直接遍历输出即可。

由于不需要排序全部，整体的时间复杂度是 O(N)。但美中不足的是：要在原数组操作，除非用 O(N)的空间来做拷贝。除此之外，针对海量动态增加的数据，也不能很好处理。这种情况需要用到“最大堆”，请前往《堆》章节查看。

3. 代码实现

function partiton(arr = [], start, end) {
  const length = arr.length;
  if (!length) {
    return null;
  }

  let v = arr[start],
    left = start + 1,
    right = end;

  while (1) {
    while (left <= end && arr[left] <= v) ++left;
    while (right >= start + 1 && arr[right] >= v) --right;

    if (left >= right) {
      break;
    }

    [arr[left], arr[right]] = [arr[right], arr[left]];
    ++left;
    --right;
  }

  [arr[right], arr[start]] = [arr[start], arr[right]];
  return right;
}

function getKthNumbers(nums = [], k) {
  if (k <= 0) {
    return null;
  }

  const length = nums.length;
  const result = new Array(k);
  let start = 0,
    end = length - 1;
  let index = partiton(nums, start, end);
  while (index !== k - 1) {
    if (index > k - 1) {
      // 前k个元素在 [start, index] 下标范围内
      // 要进一步处理，缩小区间
      end = index - 1;
      index = partiton(nums, start, end);
    } else {
      // [start, index]都属于小于k的元素，但不是全部
      // 剩下要处理的区间是 [index + 1, end]
      start = index + 1;
      index = partiton(nums, start, end);
    }
  }

  for (let i = 0; i < k; ++i) {
    result[i] = nums[i];
  }

  return result;
}

/**
 * 以下是测试代码
 */

console.log(getKthNumbers([4, 5, 1, 6, 2, 7, 3, 8], 4)); // output: [2, 3, 1, 4]
console.log(getKthNumbers([10, 2], 1));