找出数组中最小的 k 个数

1. 问题描述

我们希望从一个包含 n 个数字的数组中找出最小的 k 个元素，并以非降序返回。

举个例子，如果数组是 a = [1, 20, -30, 0, 11, 1, 503]，且 k = 3，那么结果应该是 [-30, 0, 1]，因为这是数组中最小的三个数。

当 k = 1 时，问题就退化为找出数组中最小值，这可以通过一次遍历完成。

2. 常见解法

2.1 暴力遍历法（不推荐）

做法：循环 k 次，每次找出当前最小值并从数组中移除。
时间复杂度：O(n * k)
缺点：效率低，尤其当 n 很大时，重复遍历开销大。

2.2 全排序后取前 k 个（不推荐）

做法：对整个数组排序，然后取前 k 个。
时间复杂度：O(n log n)
缺点：即使我们只需要 k 个元素，也要对整个数组排序，浪费资源。
适用场景：k 接近 n 时可以接受。

3. 基于最小堆（Min-Heap）的解法 ✅

做法：
1. 构建一个最小堆。
2. 弹出堆顶 k 次，每次弹出的是当前最小值。
时间复杂度分析：
- 构建堆：O(n)
- 弹出 k 次：O(k log n)
- 总复杂度：O(n + k log n)
优点：适用于 k 远小于 n 的情况。
实现示例（Java）：

public static int[] findKSmallestWithMinHeap(int[] nums, int k) {
    PriorityQueue<Integer> minHeap = new PriorityQueue<>();
    for (int num : nums) {
        minHeap.offer(num);
    }

    int[] result = new int[k];
    for (int i = 0; i < k; i++) {
        result[i] = minHeap.poll();
    }
    return result;
}

4. 基于最大堆（Max-Heap）的解法 ✅

做法：
1. 使用最大堆维护当前最小的 k 个数。
2. 遍历数组时，如果当前数小于堆顶，替换堆顶并重新堆化。
时间复杂度分析：
- 构建初始堆：O(k)
- 遍历剩下的 n - k 个元素，每次堆操作为 O(log k)，最坏情况下总共 O((n - k) log k)
- 总复杂度：O(n log k)
优点：适用于 k 较小的情况，节省内存。
实现示例（Java）：

public static int[] findKSmallestWithMaxHeap(int[] nums, int k) {
    PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
    for (int i = 0; i < k; i++) {
        maxHeap.offer(nums[i]);
    }

    for (int i = k; i < nums.length; i++) {
        if (nums[i] < maxHeap.peek()) {
            maxHeap.poll();
            maxHeap.offer(nums[i]);
        }
    }

    int[] result = new int[k];
    for (int i = 0; i < k; i++) {
        result[i] = maxHeap.poll();
    }
    return result;
}

5. QuickSelSort 解法 ✅

做法：
1. 使用 QuickSelect 找到第 k 小的元素。
2. 将该元素前的 k - 1 个数排序。
时间复杂度：
- 最坏情况：O(n²)
- 平均情况：O(n + k log k)
优点：
- 利用已有的排序库函数，实现简单。
- 平均性能较好。
适用场景：k 较小且数据分布较均匀时。

6. Partial QuickSort 解法 ✅

做法：
1. 使用类似 QuickSort 的分区策略。
2. 只对可能包含最小 k 个数的部分进行递归排序。
时间复杂度：
- 最坏情况：O(n²)
- 平均情况：O(n + k log k)
优点：
- 相比完整 QuickSort 更高效。
- 实际运行速度优于 QuickSelSort。
实现要点：根据分区结果决定是否递归左右子数组。

7. 使用 Median of Medians 的 Partial QuickSort ✅

做法：
1. 使用 Median of Medians 算法选择 pivot，以保证分区平衡。
2. 避免最坏情况 O(n²)，优化为 O(n + k log k)
时间复杂度：
- 最坏情况：O(n + k log k)
缺点：
- 实际运行比随机 pivot 的版本慢（因为 MoM 有额外开销）。
适用场景：对最坏情况有严格要求的场景。

8. Hybrid Partial QuickSort ✅

做法：
1. 默认使用随机 pivot。
2. 如果发现分区效率差，切换为 Median of Medians。
时间复杂度：
- 最坏情况：O(n + k log k)
- 平均情况：O(n + k log k)
优点：
- 结合了随机 pivot 的高效与 MoM 的稳定性。
- 实际运行快于纯 MoM 实现。
适用场景：对性能和稳定性都有要求的场景。

9. 其他方法

9.1 MergeSort 改造

类似 QuickSort，可以将 MergeSort 改造为只处理包含最小 k 个数的部分。
时间复杂度：O(n log n)，但实现复杂。

9.2 Floyd–Rivest 选择算法 ✅

一种比 QuickSelect 更快的选第 k 小数的算法。
适用于 k 很小的情况。
时间复杂度：平均比 QuickSelect 更优。

10. 总结对比

方法	最坏时间复杂度	平均时间复杂度	适用场景
Min-Heap	`O(n + k log n)`	`O(n + k log n)`	`k` 远小于 `n`
Max-Heap	`O(n log k)`	`O(n log k)`	内存有限，`k` 小
QuickSelSort	`O(n²)`	`O(n + k log k)`	一般场景
Partial QuickSort	`O(n²)`	`O(n + k log k)`	数据分布均匀时
Partial QuickSort + MoM	`O(n + k log k)`	`O(n + k log k)`	要求最坏性能
Hybrid Partial QuickSort	`O(n + k log k)`	`O(n + k log k)`	综合性能最佳

11. 选择建议

k 很小：使用最大堆或 Floyd–Rivest 算法。
**k 接近 n**：使用排序后取前 k 个。
一般情况：推荐使用 Hybrid Partial QuickSort。
追求稳定性：使用 MoM + Partial QuickSort。

12. 结论

本文介绍了多种找出数组中最小 k 个数的方法，涵盖了从暴力解法到堆、QuickSelect、QuickSort 改进等主流算法。在实际开发中，应根据数据规模、分布特性以及性能要求选择合适的方法。堆适用于内存敏感场景，QuickSort 改进版在大多数情况下表现良好，而 MoM 或 Hybrid 版本则在最坏情况下提供更强保障。

Persistence

REST

Security