最小的k个数

给定一个长度为 n 的可能有重复值的数组，找出其中不去重的最小的 k 个数。

例如数组元素是4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4(任意顺序皆可)。

数据范围：0≤k,n≤10000，数组中每个数的大小：0≤val≤1000

要求：空间复杂度O(n) ，时间复杂度O(nlogk)

示例：

#输入：
#[4,5,1,6,2,7,3,8],4
#返回值：
#[1,2,3,4]
#说明：
#返回最小的4个数即可，返回[1,3,2,4]也可以

刷题思路

方案一：

数组升序排序
获取前k个数

最直接的方案，但是复杂度可能不满足

方案二：

基于冒泡排序，从后往前排
循环k次，找出最小的k个

方案三：

基于选择排序，从前往后找
循环k次，找出最小的k个

方案四：

利用堆排序，每次获取最小的一个
重复k次堆排序，输出

时间复杂度小，同时需要创建树、维护小根堆，有难度

代码实现

/*
 * @Description: 最小的K个数
 * @Version: Beta1.0
 * @Author: 微信公众号：储凡
 * @Date: 2021-04-28 23:12:33
 * @LastEditors: 微信公众号：储凡
 * @LastEditTime: 2021-04-28 23:35:30
 */

/**
 * 先排序，后截取（偷懒做法）
 */
function getLeastNumbersOne(input, k) {
  // 直接基于快排，最快速的拿到排序结果也行
  return input.sort((a, b) => a - b).slice(0, k)
}

/**
 * 基于冒泡排序，跑K趟即可
 */
function getLeastNumbersTwo(input, k) {
  const len = input.length
  // 添加参数校验
  if (k > len) {
    return []
  }
  // 先将输入的数组进行排序从小到大  只排前面几个即可
  // 这里首先想到的是冒泡或者插入排序里面的特性 --- 每次都有一个元素在最终的位置上

  // 循环k次，跑k趟
  for (let index = 0; index < k; index++) {
    // 从后往前找
    for (let j = len - 1; j > index; j--) {
      if (input[index] > input[j]) {
        // 找到比它小的，位置交换
        [input[index], input[j]] = [input[j], input[index]]
      }
    }
  }
  // 排序完毕，输入前k个
  return input.slice(0, k)
}

/**
 * 基于选择排序
 */
function getLeastNumbersThree(input, k) {
  const len = input.length
  for (let i = 0; i < k; i++) {
    // 从前往后找
    for (let j = i; j < len; j++) {
      if (input[i] > input[j]) {
        // 位置互换，从小到大
        [input[i], input[j]] = [input[j], input[i]]
      }
    }
  }

  // 找出前k个
  return input.slice(0, k)
}

/**
 * 基于堆排序
 */
export function getLeastNumbersFour(input, k) {
  // todo 构建树 维护小根堆
  console.log(input, k)
}

const testArr = [4, 5, 1, 6, 2, 7, 3, 8]

getLeastNumbersOne(testArr, 4)
getLeastNumbersTwo(testArr, 4)
getLeastNumbersThree(testArr, 4)

一些建议

熟练掌握常见排序算法，尤其是：快速排序，很实用
大小根堆概念要熟知

最小的k个数

最小的k个数

题目链接

题目描述

刷题思路

代码实现

一些建议