# 最小K个数-中等

最小K个数-中等

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

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

0 <= len(arr) <= 100000
0 <= k <= min(100000, len(arr))
1
2
3
4
5
6
7
8
9

# 方法1: 暴力法

复杂度分析

  • 时间复杂度:O(nlogn),其中 n 是数组 arr 的长度。算法的时间复杂度即排序的时间复杂度。
  • 空间复杂度:O(logn),排序所需额外的空间复杂度为 O(logn)。
// 排序后取前k个
var smallestK = function(arr, k) {
  return arr.sort((a, b) => a - b).slice(0, k)
};
1
2
3
4

# 方法2: 快排思想

// https://leetcode-cn.com/problems/smallest-k-lcci/solution/zui-xiao-kge-shu-by-leetcode-solution-o5eg/
function smallestK(arr, k) {
  randomizedSelected(arr, 0, arr.length - 1, k);
  var vec = new Array(k);
  for (let i = 0; i < k; ++i) {
    vec[i] = arr[i];
  }
  return vec;
}

function randomizedSelected(arr, l, r, k) {
  if (l >= r) {
    return;
  }
  let pos = randomizedPartition(arr, l, r);
  let num = pos - l + 1;
  if (k === num) {
    return;
  } else if (k < num) {
    randomizedSelected(arr, l, pos - 1, k);
  } else {
    randomizedSelected(arr, pos + 1, r, k - num);
  }
}

// 基于随机的划分
function randomizedPartition(nums, l, r) {
  let i = l + Math.floor(Math.random() * (r - l));
  swap(nums, r, i);
  return partition(nums, l, r);
}

function partition(nums, l, r) {
  let pivot = nums[r];
  let i = l - 1;
  for (let j = l; j <= r - 1; ++j) {
    if (nums[j] <= pivot) {
      i = i + 1;
      swap(nums, i, j);
    }
  }
  swap(nums, i + 1, r);
  return i + 1;
}

function swap(nums, i, j) {
  let temp = nums[i]
  nums[i] = nums[j]
  nums[j] = temp
}
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
50