剑指 Offer 40. 最小的K个数

发表于 分类于

问题描述

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

限制：

  • 0 <= k <= arr.length <= 10000
  • 0 <= arr[i] <= 10000

解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
/*
 * @Description: 剑指 Offer 40. 最小的k个数
 * @Author: libk
 * @Github: https://github.com/libk
 */
/**
 * @param {number[]} arr
 * @param {number} k
 * @return {number[]}
 */
const getLeastNumbers = function (arr, k) {
  let left = 0
  let right = arr.length - 1
  let res = []

  const partition = (arr, left, right) => {
    let random = Math.floor(Math.random() * (right - left + 1)) + left
    let povit = arr[random]

    ;[arr[random], arr[left]] = [arr[left], arr[random]]
    while (left < right) {
      while (left < right && arr[right] >= povit) {
        right--
      }
      if (left < right) {
        arr[left++] = arr[right]
      }
      while (left < right && arr[left] < povit) {
        left++
      }
      if (left < right) {
        arr[right--] = arr[left]
      }
    }
    arr[left] = povit
    return left
  }

  while (true) {
    let index = partition(arr, left, right)
    if (index === k) {
      return arr.slice(0, k)
    } else if (index > k) {
      right = index - 1
    } else {
      left = index + 1
    }
  }
}