题目分析

虽然这题在 leetcode 上标注的「简单」，但是本题还是很有研究意义的。本文介绍了 3 种解法，时间复杂度依次降低，都是基于经典的算法或者数据结构。

解法 1: 直接排序

先说最简单、最直观的做法：直接排序。将数组按照从小到大的顺序排序，并且返回前 k 个数字。代码实现如下：

复制
1/**
2 * @param {number[]} arr
3 * @param {number} k
4 * @return {number[]}
5 */
6var getLeastNumbers = function(arr, k) {
7    return arr.sort((a, b) => a - b).slice(0, k);
8};

使用高级排序（代码用的是快排），时间复杂度是O(NlogN)，空间复杂度是O(logN)。

解法 2: 最大堆

堆是一种非常常用的数据结构。最大堆的性质是：节点值大于子节点的值，堆顶元素是最大元素。利用这个性质，整体的算法流程如下：

• 创建大小为 k 的最大堆
• 将数组的前 k 个元素放入堆中
• 从下标 k 继续开始依次遍历数组的剩余元素：
  • 如果元素小于堆顶元素，那么取出堆顶元素，将当前元素入堆
  • 如果元素大于/等于堆顶元素，不做操作

由于堆的大小是 K，空间复杂度是O(K)，时间复杂度是O(NlogK)。

由于 JavaScript 中没有堆，所以需要手动实现。代码如下：

复制
1function swap(arr, i, j) {
2    [arr[i], arr[j]] = [arr[j], arr[i]];
3}
4
5class MaxHeap {
6    constructor(arr = []) {
7        this.container = [];
8        if (Array.isArray(arr)) {
9            arr.forEach(this.insert.bind(this));
10        }
11    }
12
13    insert(data) {
14        const { container } = this;
15
16        container.push(data);
17        let index = container.length - 1;
18        while (index) {
19            let parent = Math.floor((index - 1) / 2);
20            if (container[index] <= container[parent]) {
21                break;
22            }
23            swap(container, index, parent);
24            index = parent;
25        }
26    }
27
28    extract() {
29        const { container } = this;
30        if (!container.length) {
31            return null;
32        }
33
34        swap(container, 0, container.length - 1);
35        const res = container.pop();
36        const length = container.length;
37        let index = 0,
38            exchange = index * 2 + 1;
39
40        while (exchange < length) {
41            // 如果有右节点，并且右节点的值大于左节点的值
42            let right = index * 2 + 2;
43            if (right < length && container[right] > container[exchange]) {
44                exchange = right;
45            }
46            if (container[exchange] <= container[index]) {
47                break;
48            }
49            swap(container, exchange, index);
50            index = exchange;
51            exchange = index * 2 + 1;
52        }
53
54        return res;
55    }
56
57    top() {
58        if (this.container.length) return this.container[0];
59        return null;
60    }
61}
62
63/**
64 * @param {number[]} arr
65 * @param {number} k
66 * @return {number[]}
67 */
68var getLeastNumbers = function(arr, k) {
69    const length = arr.length;
70    if (k >= length) {
71        return arr;
72    }
73
74    const heap = new MaxHeap(arr.slice(0, k));
75    for (let i = k; i < length; ++i) {
76        if (heap.top() > arr[i]) {
77            heap.extract();
78            heap.insert(arr[i]);
79        }
80    }
81    return heap.container;
82};

解法 3: 基于快速排序的 partition

解法 1 中使用了快速排序，但其实并需要对全部元素进行排序，题目只需要前 k 个元素。

回顾快速排序中的 partition 操作，可以将元素arr[0]放入排序后的正确位置，并且返回这个位置index。利用 partition 的特点，算法流程如下：

• 如果index = k，说明第 k 个元素已经放入正确位置，返回前 k 个元素
• 如果k < index，前 k 个元素在[left, index - 1]之间，缩小查找范围，继续查找
• 如果index < k，前 k 个元素在[index + 1, right] 之间，缩小查找范围，继续查找

为了方便理解，可以使用2, 8, 1, 1, 0, 11, -1, 0这个例子在纸上画一下过程。

代码实现如下：

复制
1/**
2 *
3 * @param {number[]} arr
4 * @param {number} start
5 * @param {number} end
6 * @return {number}
7 */
8function partition(arr, start, end) {
9    const k = arr[start];
10    let left = start + 1,
11        right = end;
12    while (1) {
13        while (left <= end && arr[left] <= k) ++left;
14        while (right >= start + 1 && arr[right] >= k) --right;
15
16        if (left >= right) {
17            break;
18        }
19
20        [arr[left], arr[right]] = [arr[right], arr[left]];
21        ++left;
22        --right;
23    }
24    [arr[right], arr[start]] = [arr[start], arr[right]];
25    return right;
26}
27
28/**
29 * @param {number[]} arr
30 * @param {number} k
31 * @return {number[]}
32 */
33var getLeastNumbers = function(arr, k) {
34    const length = arr.length;
35    if (k >= length) return arr;
36    let left = 0,
37        right = length - 1;
38    let index = partition(arr, left, right);
39    while (index !== k) {
40        if (index < k) {
41            left = index + 1;
42            index = partition(arr, left, right);
43        } else if (index > k) {
44            right = index - 1;
45            index = partition(arr, left, right);
46        }
47    }
48
49    return arr.slice(0, k);
50};

时间复杂度是O(N)，空间复杂度是O(N)。