最小K个数

题目

LeetCode 中等

TIP

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

INFO

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

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

题解

方法： sort

O(nlogn) O(logn)

function getLeastNumbers(arr: number[], k: number): number[] {
  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))

方法：堆排序

O(nlogk) O(k)

function getLeastNumbersHeap(nums: number[], k: number): number[] {
  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: number): void {
    for (let i = Math.floor(heapSize / 2) - 1; i >= 0; i--) {
      maxHeapify(i, heapSize)
    }
  }
  // 从左向右，自上而下的调整节点
  function maxHeapify(i: number, heapSize: number): void {
    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: number[], i: number, j: number) {
    ;[arr[i], arr[j]] = [arr[j], arr[i]]
  }
}

const arr2 = [0, 0, 0, 1, 2, 2, 3, 7, 6, 1],
  k2 = 3
console.log('🌰', getLeastNumbersHeap(arr2, k2))

方法：快排的优化版

O(n) O(n)

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

  function quickSort(left: number, right: number) {
    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: number[], i: number, j: number) {
      ;[arr[i], arr[j]] = [arr[j], arr[i]]
    }
  }
}

const arr3 = [0, 1, 1, 2, 4, 4, 1, 3, 3, 2],
  k3 = 6
console.log('🌰', getLeastNumbersQuickSelect(arr3, k3))