题⽬描述
输⼊ n 个整数，找出其中最⼩的 K 个数。例如输⼊ 4,5,1,6,2,7,3,8 这 8 个数字，则最⼩的 4 个数字是 1,2,3,4 。
思路及解答
排序法
最直接的思路是将数组排序后取前k个元素
public ArrayList<Integer> GetLeastNumbers_Solution(int[] input, int k) {
ArrayList<Integer> result = new ArrayList<>();
if (input == null || k <= 0 || k > input.length) {
return result; // 处理非法输入
}
Arrays.sort(input); // 使用Java内置排序，时间复杂度O(n log n)
for (int i = 0; i < k; i++) {
result.add(input[i]); // 取前k个元素
}
return result;
}- 时间复杂度：主要由
Arrays.sort()决定，为 O(n log n) - 空间复杂度：O(k)，用于存储结果的列表
大顶堆法（推荐）
大顶堆法的核心思想是：始终维护一个大小为 K 的候选集合，这个集合中保存当前遍历过的元素里最小的 K 个数。
这⾥不展开最⼤堆和最⼩堆的具体讲解，什么是最⼤堆/最⼩堆呢？
- ⼤/⼩堆树是完全⼆叉树
- ⼤/⼩堆树的每⼀个节点不⼩于/不⼤于其孩⼦节点。
因为使用的是大顶堆，所以堆顶 heap.peek() 是这 K 个候选数中的最大值。遍历数组时，如果堆的大小还不到 K，就直接把当前数加入堆中。
当堆已经有 K 个元素时，只需要将当前数 num 和堆顶比较：
- 如果 num < heap.peek()，说明当前数比候选集合中最大的数还小，应该进入结果集合。此时移除堆顶，再加入 num。
- 如果 num >= heap.peek()，说明当前数不可能属于最小的 K 个数，直接跳过。
遍历结束后，堆中剩下的 K 个元素就是最小的 K 个数。需要注意的是，堆中的元素不一定是有序的，如果题目要求升序输出，可以再对结果排序。
public ArrayList<Integer> GetLeastNumbers_Solution(int[] input, int k) {
ArrayList<Integer> result = new ArrayList<>();
if (input == null || k <= 0 || k > input.length) {
return result;
}
// 创建一个大顶堆，使用自定义比较器实现降序排列
PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a);
for (int num : input) {
if (maxHeap.size() < k) {
maxHeap.offer(num); // 堆未满，直接加入
} else if (num < maxHeap.peek()) { // 当前数比堆顶最大值小
maxHeap.poll(); // 移除堆顶最大值
maxHeap.offer(num); // 将当前数加入堆
}
}
result.addAll(maxHeap);
return result;
}- 时间复杂度：O(n log k)。每次插入或删除堆的操作需要 O(log k) 时间，共需进行 n 次这样的操作
- 空间复杂度：O(k)，堆的大小
堆这种数据结构适合处理海量数据（数据无法一次性装入内存），或者当 k 远小于 n 时非常高效。
大数据问题处理面试题：https://www.seven97.top/interview/intelligence-massivedata/massivedataprocessing.html
快速选择法（效率最优）
QuickSelect 的核心来自快速排序中的 partition 操作。每次选择一个基准值 pivot，把数组划分成两部分：左边都小于等于 pivot，右边都大于等于 pivot。partition 会返回 pivot 的最终下标 pivotIndex。
如果 pivotIndex == k - 1，说明 pivot 已经处在第 k 小的位置上，它左边的 k - 1 个数加上它本身，正好就是最小的 k 个数。
如果 pivotIndex > k - 1，说明第 k 小的位置在 pivot 左边，最小的 k 个数也一定都在左侧区间，因此只需要继续处理左半部分。
如果 pivotIndex < k - 1，说明左边的元素数量还不够 k 个，最小的 k 个数还需要从右侧补一部分，因此继续处理右半部分。
和快速排序不同，QuickSelect 每次只递归一边，所以平均时间复杂度是 O(n)。最终数组前 k 个位置保存的就是最小的 k 个数，但它们内部不一定有序。
public ArrayList<Integer> GetLeastNumbers_Solution(int[] input, int k) {
ArrayList<Integer> result = new ArrayList<>();
if (input == null || k <= 0 || k > input.length) {
return result;
}
quickSelect(input, 0, input.length - 1, k);
for (int i = 0; i < k; i++) {
result.add(input[i]);
}
return result;
}
private void quickSelect(int[] arr, int left, int right, int k) {
if (left >= right) return;
int pivotIndex = partition(arr, left, right);
if (pivotIndex == k - 1) { // 基准点正好是第k-1个位置（0-indexed），则其左边就是最小的k个数
return;
} else if (pivotIndex > k - 1) { // 基准点位置大于k-1，说明最小的k个数在左边
quickSelect(arr, left, pivotIndex - 1, k);
} else { // 基准点位置小于k-1，说明最小的k个数还需要包括右边的一部分
quickSelect(arr, pivotIndex + 1, right, k);
}
}
// 分区操作，将小于基准的数放在左边，大于基准的数放在右边，返回基准的最终位置
public static int partition(int[] array, int low, int high) {
// 1. 随机选择基准，避免最坏情况（例如数组已经有序时退化成 O(n²)）
Random random = new Random();
int randomIndex = random.nextInt(high - low + 1) + low;
// 将随机选中的基准值先交换到数组的最末尾，方便后续统一处理
swap(array, randomIndex, high);
// 2. 取最后一个元素（也就是刚才随机选出来的基准）作为中心元素
int pivot = array[high];
// 定义指针，指向比中心元素大的第一个位置（即“小元素区”的下一个位置）
int pointer = low;
// 3. 遍历数组中的所有元素，将比中心元素小的放在左边，大的自然留在右边
for (int i = low; i < high; i++) {
if (array[i] <= pivot) {
// 如果当前元素比基准小（或相等），就把它交换到 pointer 指向的位置
// 此时 pointer 左边全是小于等于 pivot 的元素
swap(array, i, pointer);
pointer++; // 指针右移，扩大“小元素区”
}
}
// 4. 遍历结束后，pointer 指向的位置就是基准值最终应该在的位置
// 将基准值（目前在 high 位置）和 pointer 指向的元素交换
swap(array, pointer, high);
return pointer; // 返回基准值的最终下标
}
private void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}- 时间复杂度：平均 O(n)。每次partition操作平均处理n个元素，但每次都能将问题规模大致减半（n + n/2 + n/4 + ... ≈ 2n）。最坏情况（每次选的基准都是最大或最小值）下为O(n²)，但随机选择基准有效避免了最坏情况的发生。
- 空间复杂度：O(log n)，递归调用栈的深度