zhangdizhangdi

最小K个数

题目

LeetCode 中等

原来是 剑指 offer40，原题变了。

设计一个算法，找出数组中最小的 k 个数。以任意顺序返回这 k 个数均可。

示例：
输入： arr = [1,3,5,7,2,4,6,8], k = 4
输出： [1,2,3,4]

题解

方法： sort

O(nlogn) O(logn)

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

const arr = [3, 44, 5, 32, 2, 45, 7],
  k = 3
console.log('🌰', getLeastNumbers(arr, k))
执行结果
🌰 [ 2, 3, 5 ]

方法：堆排序

O(nlogk) O(k)

js
function getLeastNumbersHeap(nums, k) {
  let heapSize = nums.length
  const len = nums.length
  buildMaxHeap(heapSize)

  console.log('init maxHeap', [...nums])

  for (let i = 0; i <= len - k - 1; i++) {
    swap(nums, 0, len - 1 - i)
    --heapSize
    maxHeapify(0, heapSize)

    console.log('', i, [...nums])
  }
  return nums.slice(0, k)

  // 自下而上构建一颗大顶堆
  function buildMaxHeap(heapSize) {
    for (let i = Math.floor(heapSize / 2) - 1; i >= 0; i--) {
      maxHeapify(i, heapSize)
    }
  }
  // 从左向右，自上而下的调整节点
  function maxHeapify(i, heapSize) {
    let l = i * 2 + 1
    let r = i * 2 + 2
    let largest = i
    if (l < heapSize && nums[l] > nums[largest]) {
      largest = l
    }
    if (r < heapSize && nums[r] > nums[largest]) {
      largest = r
    }
    if (largest !== i) {
      swap(nums, i, largest)
      maxHeapify(largest, heapSize)
    }
  }
  //交换
  function swap(arr, i, j) {
    ;[arr[i], arr[j]] = [arr[j], arr[i]]
  }
}

const arr = [0, 0, 0, 1, 2, 2, 3, 7, 6, 1],
  k = 3
console.log('🌰', getLeastNumbersHeap(arr, k))
执行结果
init maxHeap [
  7, 6, 3, 1, 2,
  2, 0, 0, 0, 1
]
 0 [
  6, 2, 3, 1, 1,
  2, 0, 0, 0, 7
]
 1 [
  3, 2, 2, 1, 1,
  0, 0, 0, 6, 7
]
 2 [
  2, 1, 2, 0, 1,
  0, 0, 3, 6, 7
]
 3 [
  2, 1, 0, 0, 1,
  0, 2, 3, 6, 7
]
 4 [
  1, 1, 0, 0, 0,
  2, 2, 3, 6, 7
]
 5 [
  1, 0, 0, 0, 1,
  2, 2, 3, 6, 7
]
 6 [
  0, 0, 0, 1, 1,
  2, 2, 3, 6, 7
]
🌰 [ 0, 0, 0 ]

方法：快排的优化版

O(n) O(n)

js
function getLeastNumbersQuickSelect(arr, k) {
  if (k < 1) return []
  quickSort(0, arr.length - 1)
  return arr.slice(0, k)

  function quickSort(left, right) {
    console.log('li', left, 'ri', right, arr)

    if (left >= right) {
      return
    }

    let pivotNum = arr[right]

    console.log('pivotNum', pivotNum)

    let i = left
    let targetIndex = left
    //从左边开始循环对比
    while (i < right) {
      if (arr[i] <= pivotNum) {
        console.log(
          '小于等于 目标值 indexs i',
          i,
          'targetIndex',
          targetIndex,
          ' | nums',
          arr[i],
          arr[targetIndex],
        )

        swap(arr, targetIndex, i)
        targetIndex++
      }
      i++
    }

    console.log(
      '--- indexs i',
      i,
      'targetIndex',
      targetIndex,
      ' | nums',
      arr[right],
      arr[targetIndex],
    )

    swap(arr, targetIndex, right)

    console.log(arr)
    console.log('----')

    if (targetIndex === k) {
      return
    } else if (targetIndex > k) {
      quickSort(left, targetIndex - 1)
    } else {
      quickSort(targetIndex + 1, right)
    }

    function swap(arr, i, j) {
      ;[arr[i], arr[j]] = [arr[j], arr[i]]
    }
  }
}

const arr = [0, 1, 1, 2, 4, 4, 1, 3, 3, 2],
  k = 6
console.log('🌰', getLeastNumbersQuickSelect(arr, k))
执行结果
li 0 ri 9 [
  0, 1, 1, 2, 4,
  4, 1, 3, 3, 2
]
pivotNum 2
小于等于 目标值 indexs i 0 targetIndex 0  | nums 0 0
小于等于 目标值 indexs i 1 targetIndex 1  | nums 1 1
小于等于 目标值 indexs i 2 targetIndex 2  | nums 1 1
小于等于 目标值 indexs i 3 targetIndex 3  | nums 2 2
小于等于 目标值 indexs i 6 targetIndex 4  | nums 1 4
--- indexs i 9 targetIndex 5  | nums 2 4
[
  0, 1, 1, 2, 1,
  2, 4, 3, 3, 4
]
----
li 6 ri 9 [
  0, 1, 1, 2, 1,
  2, 4, 3, 3, 4
]
pivotNum 4
小于等于 目标值 indexs i 6 targetIndex 6  | nums 4 4
小于等于 目标值 indexs i 7 targetIndex 7  | nums 3 3
小于等于 目标值 indexs i 8 targetIndex 8  | nums 3 3
--- indexs i 9 targetIndex 9  | nums 4 4
[
  0, 1, 1, 2, 1,
  2, 4, 3, 3, 4
]
----
li 6 ri 8 [
  0, 1, 1, 2, 1,
  2, 4, 3, 3, 4
]
pivotNum 3
小于等于 目标值 indexs i 7 targetIndex 6  | nums 3 4
--- indexs i 8 targetIndex 7  | nums 3 4
[
  0, 1, 1, 2, 1,
  2, 3, 3, 4, 4
]
----
li 6 ri 6 [
  0, 1, 1, 2, 1,
  2, 3, 3, 4, 4
]
🌰 [ 0, 1, 1, 2, 1, 2 ]