<< 返回算法列表

最小的k个数

描述 给定一个数组，找出其中最小的K个数。例如数组元素是4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4。

示例1

输入：
[4,5,1,6,2,7,3,8],4 

返回值：
[1,2,3,4]

说明：
返回最小的4个数即可，返回[1,3,2,4]也可以    

示例2

输入：
[1],0

返回值：
[]

示例3

输入：
[0,1,2,1,2],3

返回值：
[0,1,1]

解答

有两种方法推荐。

方法1: 使用快速排序，截取前k个值。 时间复杂度为O(N*logN)。 见 排序

方法2: 依次从原数组中取出数据插入到已排序数组X中，长度超出K的元素被移除。 插入可使用二分法插入，时间复杂度为logK，遍历N个元素，总时间复杂度为O(n*logK)

function GetLeastNumbers_Solution(input, k)
{
    // write code here
    let heap = []
    for(let i=0; i<input.length; i++) {
        insert(heap, input[i], 0, heap.length-1)
    }
 
    function insert(arr, value, start, end) {
      if(start === end) {
          if(arr[start] > value) {
              arr.splice(start, 0, value)
          } else {
              arr.splice(start+1, 0, value)
          }
          if(arr.length > k) arr.pop()
          return 
      }
      if(start > end) {
          arr.splice(start, 0, value)
          if(arr.length > k) arr.pop()
          return
      }
 
      let mid = ~~((start + end)/2)
      if(arr[mid] > value) {
          insert(arr, value, start, mid -1)
      } else if(arr[mid] <= value) {
          insert(arr, value, mid + 1, end)
      }
    }
    return heap
}