加载中...
面试题 17.14-最小K个数(Smallest K LCCI)
发表于:2021-12-03 | 分类: 中等
字数统计: 1.5k | 阅读时长: 6分钟 | 阅读量:

原文链接: https://leetcode-cn.com/problems/smallest-k-lcci

英文原文

Design an algorithm to find the smallest K numbers in an array.

Example:

Input:  arr = [1,3,5,7,2,4,6,8], k = 4
Output:  [1,2,3,4]

Note:

  • 0 <= len(arr) <= 100000
  • 0 <= k <= min(100000, len(arr))

中文题目

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

通过代码

高赞题解

优先队列(小根堆)

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

image.png

代码:

[]
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(k\log{n})$。整体复杂度为 $O(n\log{n})$
  • 空间复杂度:$O(n + k)$

优先队列(大根堆)

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

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

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

  • 堆内元素不足 $k$ 个:直接将 $arr[i]$ 放入堆内;
  • 堆内元素为 $k$ 个:根据 $arr[i]$ 与堆顶元素的大小关系分情况讨论:
    • $arr[i] >= heapTop$:$arr[i]$ 不可能属于第 $k$ 小数(已有 $k$ 个元素在堆中),直接丢弃 $arr[i]$;
    • $arr[i] < heapTop$:$arr[i]$ 可能属于第 $k$ 小数,弹出堆顶元素,并放入 $arr[i]$。

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

image.png

代码:

[]
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(k\log{k})$。整体复杂度为 $O(n\log{k})$
  • 空间复杂度:$O(k)$

全排序

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

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

image.png

代码:

[]
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(k)$。整体复杂度为 $O(n\log{n})$
  • 空间复杂度:$O(\log{n} + k)$

快排数组划分

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

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

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

因此我们可以通过判断基准点的下标 $idx$ 与 $k$ 的关系来确定过程是否结束:

  • $idx < k$:基准点左侧不足 $k$ 个,递归处理右边,让基准点下标右移;
  • $idx > k$:基准点左侧超过 $k$ 个,递归处理左边,让基准点下标左移;
  • $idx = k$:基准点左侧恰好 $k$ 个,输出基准点左侧元素。

image.png

代码:

[]
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; } }
  • 时间复杂度:由于每次都会随机选择基准值,因此每次递归的数组平均长度为 $n / 2$,那么划分数组操作的次数不会超过 $2 * n$。整体复杂度为 $O(n)$
  • 空间复杂度:$O(\log{n})$

最后

如果有帮助到你,请给题解点个赞和收藏,让更多的人看到 ~ (“▔□▔)/

也欢迎你 关注我(公主号后台回复「送书」即可参与长期看题解学算法送实体书活动)或 加入「组队打卡」小群 ,提供写「证明」&「思路」的高质量题解。

所有题解已经加入 刷题指南,欢迎 star 哦 ~

统计信息

通过次数 提交次数 AC比率
79632 133526 59.6%

提交历史

提交时间 提交结果 执行时间 内存消耗 语言
上一篇:
面试题 17.13-恢复空格(Re-Space LCCI)
下一篇:
面试题 17.15-最长单词(Longest Word LCCI)
本文目录
本文目录