算法：最小的k个数

以你之姓@ 2024-04-03 14:17 19阅读 0赞

![d42d543de3045d3132ea41a5defad606.jpeg][]

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

## 示例 ##

*  输入：arr = \[3,2,1\], k = 2
 *  输出：\[1,2\] 或者 \[2,1\]

## 限制 ##

*  0 <= k <= arr.length <= 10000
 *  0 <= arr\[i\] <= 10000

## 方法：数组排序 ##

对目标数组进行从小到大排序，然后取前 k 个数即可。

![8e300b91d97420a8cdbacbec07736a11.jpeg][]

**代码如下：**

![e6c5422998d97d0325c3e9341edfe7d6.jpeg][]

## 复杂度分析 ##

*  时间复杂度：O(nlogn)，其中 n 是数组 arr 的长度。算法的时间复杂度即排序的时间复杂度。

*  空间复杂度：O(logn)，排序所需额外的空间复杂度为 O(logn)。

## 方法：大根堆 ##

创建一个大根堆，把前 k 个值插入到堆中，从 K+1 开始如果当前值比 堆顶的值小，就弹出，把当前值放入到堆中，最后将堆以数组的形式返回。

![56f458753a7273d9d06e0bc645b20c06.jpeg][]

**代码如下：**

![970f335e9dc44c0c96aae41ebfd8a404.png][]

## 复杂度分析 ##

*  时间复杂度：O(nlogk)，其中 n 是数组 arr 的长度。由于大根堆实时维护前 k 小值，所以插入删除都是 O(logk) 的时间复杂度，最坏情况下数组里 n 个数都会插入，所以一共需要 O(nlogk) 的时间复杂度。
 *  空间复杂度：O(k)，因为大根堆里最多 k 个数。

## 方法：快速排序 ##

该方法出自 “K神”的题解，快速排序算法有两个核心点，分别为 “哨兵划分” 和 “递归” 。

*  哨兵划分操作： 以数组某个元素（一般选取首元素）为 基准数 ，将所有小于基准数的元素移动至其左边，大于基准数的元素移动至其右边。
 *  递归： 对 左子数组 和 右子数组 递归执行 哨兵划分，直至子数组长度为 1 时终止递归，即可完成对整个数组的排序。

**代码如下：**

![76823572732bd946921747950fcc21a3.jpeg][]

## 复杂度分析 ##

*  时间复杂度： O(NlogN) 。
 *  空间复杂度： O(N)。

## END ##

业精于勤荒于嬉，行成于思毁于随，赠友人。

好兄弟可以点赞并关注我的公众号“javaAnswer”，全部都是干货。

![4d8a4339b9574fbd9e138a4b76ae4d88.png][]

[d42d543de3045d3132ea41a5defad606.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/4aceb2595b464106a979b772d323911c.jpeg
[8e300b91d97420a8cdbacbec07736a11.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/1faa7e96159d4c3889608ed4b981355a.jpeg
[e6c5422998d97d0325c3e9341edfe7d6.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/3fa1478896d24326992dedf60da1eadd.jpeg
[56f458753a7273d9d06e0bc645b20c06.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/de4c278f49844f84be0711d4c3fc9602.jpeg
[970f335e9dc44c0c96aae41ebfd8a404.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/b6b232c913054985b20559ee80effddc.png
[76823572732bd946921747950fcc21a3.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/c374faef56fc4f46baa7020a4bb7a094.jpeg
[4d8a4339b9574fbd9e138a4b76ae4d88.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/50917a7813ea42e78ccff9d20e974d5b.png