【刷穿 LeetCode】面试题 17.14. 最小K个数:「优先队列（堆）」&「全排序」&「数组划分」-阿里云开发者社区

【刷穿 LeetCode】面试题 17.14. 最小K个数:「优先队列（堆）」&「全排序」&「数组划分」

2022-05-05 131

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 【刷穿 LeetCode】面试题 17.14. 最小K个数:「优先队列（堆）」&「全排序」&「数组划分」

网络异常，图片无法展示

题目描述

这是 LeetCode 上的 面试题 17.14. 最小K个数 ，难度为中等。

Tag : 「优先队列」、「堆」、「排序」

设计一个算法，找出数组中最小的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))

优先队列（小根堆）

一个直观的想法是使用「优先队列（小根堆）」，起始将所有元素放入堆中，然后再从堆中取出 kk 个元素并「顺序」构造答案。

网络异常，图片无法展示

代码：

class Solution {
    public int[] smallestK(int[] arr, int k) {
        PriorityQueue<Integer> q = new PriorityQueue<>((a,b)->a-b);
        for (int i : arr) q.add(i);
        int[] ans = new int[k];
        for (int i = 0; i < k; i++) ans[i] = q.poll();
        return ans;
    }
}
复制代码

时间复杂度：建堆复杂度为 O(n\log{n})O(nlogn)，构造答案复杂度为 O(k\log{n})O(klogn)。整体复杂度为 O(n\log{n})O(nlogn)
空间复杂度：O(n + k)O(n+k)

优先队列（大根堆）

在解法一中，我们将所有的原始都放入堆中，堆中元素最多有 nn 个，这导致了我们复杂度的上界为 O(n\log{n})O(nlogn)。

而另外一个比较优秀的做法是，使用「优先队列（大根堆）」。

当处理到原始 arr[i]arr[i] 时，根据堆内元素个数，以及其与堆顶元素的关系分情况讨论：

堆内元素不足 kk 个：直接将 arr[i]arr[i] 放入堆内；
堆内元素为kk个：根据arr[i]arr[i]与堆顶元素的大小关系分情况讨论：

arr[i] >= heapToparr[i]>=heapTop：arr[i]arr[i] 不可能属于第 kk 小数（已有 kk 个元素在堆中），直接丢弃 arr[i]arr[i]；
arr[i] < heapToparr[i]<heapTop：arr[i]arr[i] 可能属于第 kk 小数，弹出堆顶元素，并放入 arr[i]arr[i]。

当 arrarr 被处理完，我们再使用堆中元素「逆序」构造答案。

网络异常，图片无法展示

代码：

class Solution {
    public int[] smallestK(int[] arr, int k) {
        PriorityQueue<Integer> q = new PriorityQueue<>((a,b)->b-a);
        int[] ans = new int[k];
        if (k == 0) return ans;
        for (int i : arr) {
            if (q.size() == k && q.peek() <= i) continue;
            if (q.size() == k) q.poll();
            q.add(i);
        }
        for (int i = k - 1; i >= 0; i--) ans[i] = q.poll();
        return ans;
    }
}
复制代码

时间复杂度：建堆复杂度为 O(n\log{k})O(nlogk)，构造答案复杂度为 O(k\log{k})O(klogk)。整体复杂度为 O(n\log{k})O(nlogk)
空间复杂度：O(k)O(k)

全排序

Java 中的 Arrays.sort 为综合排序实现。会根据数据规模、元素本身是否大致有序选择不同的排序实现。

因此一个比较省事的实现是先使用 Arrays.sort 进行排序，再构造答案。

网络异常，图片无法展示

代码：

class Solution {
    public int[] smallestK(int[] arr, int k) {
        Arrays.sort(arr);
        int[] ans = new int[k];
        for (int i = 0; i < k; i++) ans[i] = arr[i];
        return ans;
    }
}
复制代码

时间复杂度：排序（假定 Arrays.sort 使用的是双轴快排实现）的复杂度为 O(n\log{n})O(nlogn)；构造答案复杂度为 O(k)O(k)。整体复杂度为 O(n\log{n})O(nlogn)
空间复杂度：O(\log{n} + k)O(logn+k)

快排数组划分

注意到题目要求「任意顺序返回这 kk 个数即可」，因此我们只需要确保前 kk 小的数都出现在下标为 [0, k)[0,k) 的位置即可。

利用「快速排序」的数组划分即可做到。

我们知道快排每次都会将小于等于基准值的值放到左边，将大于基准值的值放到右边。

因此我们可以通过判断基准点的下标 idxidx 与 kk 的关系来确定过程是否结束：

idx < kidx<k：基准点左侧不足 kk 个，递归处理右边，让基准点下标右移；
idx > kidx>k：基准点左侧超过 kk 个，递归处理左边，让基准点下标左移；
idx = kidx=k：基准点左侧恰好 kk 个，输出基准点左侧元素。

网络异常，图片无法展示

代码：

class Solution {
    int k;
    public int[] smallestK(int[] arr, int _k) {
        k = _k;
        int n = arr.length;
        int[] ans = new int[k];
        if (k == 0) return ans;
        qsort(arr, 0, n - 1);
        for (int i = 0; i < k; i++) ans[i] = arr[i];
        return ans;
    }
    void qsort(int[] arr, int l, int r) {
        if (l >= r) return ;
        int i = l, j = r;
        int ridx = new Random().nextInt(r - l + 1) + l;
        swap(arr, ridx, l);
        int x = arr[l];
        while (i < j) {
            while (i < j && arr[j] >= x) j--;
            while (i < j && arr[i] <= x) i++;
            swap(arr, i, j);
        }
        swap(arr, i, l);
        // 集中答疑：因为题解是使用「基准点左侧」来进行描述（不包含基准点的意思），所以这里用的 k（写成 k - 1 也可以滴
        if (i > k) qsort(arr, l, i - 1);
        if (i < k) qsort(arr, i + 1, r);
    }
    void swap(int[] arr, int l, int r) {
        int tmp = arr[l];
        arr[l] = arr[r];
        arr[r] = tmp;
    }
}
复制代码