【JS】最小的K个数

快排。模板套路就行了。

function GetLeastNumbers_Solution(input, k)
{
  // 异常数据
  if (k > input.length || k <= 0) return [];
  return quickSearch(input, 0, input.length - 1, k - 1);
}

function quickSearch(a, low, high, k) {
  let p = part(a, low, high);
  if (p === k) {
    // 这里主要考虑到面试官可能限制使用本身的sort函数
    return part(a.slice(0, k + 1), 0, k, true);
  }
  return p > k ? quickSearch(a, low, p - 1, k) : quickSearch(a, p + 1, high, k);
}

// findRes 是为了能复用函数
function part(a, low, high, findRes = false) {
  if (low >= high && findRes) return a;
  let p = a[low];
  let i = low;
  let j = high + 1;
  while (true) {
    while (++i <= high && a[i] < p) ;
    while (--j >= low && a[j] > p) ;
    if (i >= j) break;
    let temp = a[i];
    a[i] = a[j];
    a[j] = temp;
  }
  a[low] = a[j];
  a[j] = p;
  if (findRes) {
    part(a, low, j - 1, findRes);
    part(a, j + 1, high, findRes);
    return a;
  }
  return j;
}

module.exports = {
    GetLeastNumbers_Solution : GetLeastNumbers_Solution
};