😀前言
在编程面试中，找出一个数组中最小的K个数是一个常见的问题。虽然看似简单，但要在高效性方面有所保证却并不容易。本文将介绍两种有效解决该问题的算法：基于堆的解法和快速选择算法。我们将详细讲解它们的实现方式、时间复杂度分析以及适用场景，帮助你在面试中从容应对这一问题。

🏠个人主页：尘觉主页

最小的 K 个数

题目链接

牛客网

问题描述

给定一个长度为n的数组，数组中可能包含重复值。要求找出其中不去重的最小的k个数。例如，给定数组 [4,5,1,6,2,7,3,8] 和 k=4，则返回 [1,2,3,4]（任意顺序皆可）。

数据范围和要求

• 数据范围：0≤k,n≤10000，数组中每个数的大小在0到1000之间。
• 时间复杂度要求：O(nlogk)
• 空间复杂度要求：O(n)

方法一：基于堆的解法

堆是一种适合处理部分排序问题的数据结构。在本题中，我们使用大顶堆来维护最小的k个数。

具体思路

1. 创建一个大小为k的大顶堆，用于存储当前找到的最小的k个数。
2. 遍历数组元素，将每个元素加入大顶堆。
3. 如果堆的大小超过k，则将堆顶元素移除。堆顶元素是堆中最大的数，这样可以确保堆中存储的都是当前最小的k个数。

在Java中，我们可以使用PriorityQueue类实现堆，并在初始化时通过Lambda表达式(o1, o2) -> o2 - o1来构建大顶堆。

import java.util.ArrayList;
import java.util.PriorityQueue;public class Solution {public ArrayList<Integer> GetLeastNumbers_Solution(int[] nums, int k) {// 如果k大于数组长度或k小于等于0，直接返回空的结果if (k > nums.length || k <= 0) {return new ArrayList<>();}// 创建一个大顶堆，用于存储最小的k个数PriorityQueue<Integer> maxHeap = new PriorityQueue<>((o1, o2) -> o2 - o1);// 遍历数组中的每个元素for (int num : nums) {// 将元素加入大顶堆maxHeap.add(num);// 如果堆的大小超过k，移除堆顶元素（即最大元素）if (maxHeap.size() > k) {maxHeap.poll();}}// 将堆中的元素转为ArrayList返回return new ArrayList<>(maxHeap);}
}

时间复杂度分析

在此算法中，维护堆的插入和删除操作的时间复杂度为O(logk)。因此，遍历整个数组的时间复杂度为O(nlogk)，最终的空间复杂度为O(k)，这是由于堆的存储占用的空间。

适用场景

这种基于堆的解法特别适合处理大规模数据，尤其是当k较小且数据量n较大时，它的效率优势更加明显。

方法二：快速选择算法

快速选择算法基于快速排序的思想，通过分治法快速找到第k个最小的元素，并将前k个元素放在数组的前k个位置上。

具体思路

1. 使用快速排序的partition()方法，将数组分割成两部分，其中一部分比选定的pivot小，另一部分比pivot大。
2. 通过调整pivot的位置，可以快速定位到第k个最小的元素。
3. 最终数组的前k个元素即为最小的k个数。

代码实现

import java.util.ArrayList;public class Solution {public ArrayList<Integer> GetLeastNumbers_Solution(int[] nums, int k) {ArrayList<Integer> ret = new ArrayList<>();// 如果k大于数组长度或k小于等于0，直接返回空的结果if (k > nums.length || k <= 0) {return ret;}// 使用快速选择算法找到第k个最小元素findKthSmallest(nums, k - 1);// 将前k个元素加入结果列表for (int i = 0; i < k; i++) {ret.add(nums[i]);}return ret;}// 快速选择算法，找到数组中第k个最小的元素public void findKthSmallest(int[] nums, int k) {int l = 0, h = nums.length - 1;while (l < h) {// 调用partition方法对数组进行分区int j = partition(nums, l, h);// 如果找到的分区位置正好是k，则停止if (j == k) {break;}// 如果分区位置大于k，调整高位指针if (j > k) {h = j - 1;} else {// 如果分区位置小于k，调整低位指针l = j + 1;}}}// partition方法对数组进行分区，使得左边元素小于pivot，右边元素大于pivotprivate int partition(int[] nums, int l, int h) {int p = nums[l];  // 选取数组的第一个元素作为pivotint i = l, j = h + 1;while (true) {// 从左向右找到第一个大于pivot的元素while (i != h && nums[++i] < p);// 从右向左找到第一个小于pivot的元素while (j != l && nums[--j] > p);// 如果左右指针交错，退出循环if (i >= j) {break;}// 交换这两个元素的位置swap(nums, i, j);}// 最后将pivot放到正确的位置swap(nums, l, j);return j;  // 返回pivot的位置}// 交换数组中两个元素的位置private void swap(int[] nums, int i, int j) {int t = nums[i];nums[i] = nums[j];nums[j] = t;}
}

时间复杂度分析

快速选择算法的时间复杂度为O(n)，空间复杂度为O(1)，因为它直接在原数组上进行修改，而不需要额外的存储空间。

适用场景

这种方法在需要快速得到结果且允许修改数组的情况下非常有效。如果数组不可修改，建议使用堆的解法。

😄总结

通过对比，我们可以看到两种方法各有优劣。堆的解法适用于大规模数据和较小的k值场景，而快速选择算法在需要快速得到结果且允许修改数据时更加高效。根据具体需求选择适合的算法，能够更好地解决问题，提升面试表现。

😁热门专栏推荐
想学习vue的可以看看这个

java基础合集

数据库合集

redis合集

nginx合集

linux合集

手写机制

微服务组件

spring_尘觉

springMVC

mybits

等等等还有许多优秀的合集在主页等着大家的光顾感谢大家的支持

🤔欢迎大家加入我的社区 尘觉社区

文章到这里就结束了，如果有什么疑问的地方请指出，诸佬们一起来评论区一起讨论😁
希望能和诸佬们一起努力，今后我们一起观看感谢您的阅读🍻
如果帮助到您不妨3连支持一下，创造不易您们的支持是我的动力🤞