最小的k个数

40. 最小的 k 个数

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

示例 1:

输入：arr = [3,2,1], k = 2
输出：[1,2] 或者 [2,1]

示例 2:

输入：arr = [0,1,2,1], k = 1
输出：[0]

答案

sort API

var getLeastNumbers = function(arr, k) {
    return arr.sort((a, b) => a - b).slice(0, k)
};

快速排序

const arr = [3,2,1]
const k = 2

function quickSort(arr) {
  if(arr.length <= 1)return arr
  // 中间值
  var pivotIndex = Math.floor(arr.length/2)
  var pivot = arr.splice(pivotIndex,1)[0]

  var left = []
  var right = []
  for(let i=0;i<arr.length;i++){
    if(arr[i] < pivot){
      left.push(arr[i])
    }else{
      right.push(arr[i])
    }
  }

  return quickSort(left).concat([pivot],quickSort(right))
}

var getLeastNumbers = function (arr, k) {
  return quickSort(arr).slice(0,k)
}

console.log(getLeastNumbers(arr,k))