剑指offer-29、最⼩的k个数

题⽬描述

输⼊ n 个整数，找出其中最⼩的 K 个数。例如输⼊ 4,5,1,6,2,7,3,8 这 8 个数字，则最⼩的 4 个数字是 1,2,3,4 。
思路及解答

排序法

最直接的思路是将数组排序后取前k个元素

1. public ArrayList<Integer> GetLeastNumbers_Solution(int[] input, int k) {
2.     ArrayList<Integer> result = new ArrayList<>();
3.     if (input == null || k <= 0 || k > input.length) {
4.         return result; // 处理非法输入
5.     }
6.     Arrays.sort(input); // 使用Java内置排序，时间复杂度O(n log n)
7.     for (int i = 0; i < k; i++) {
8.         result.add(input[i]); // 取前k个元素
9.     }
10.     return result;
11. }

复制代码

• ​时间复杂度​：主要由 Arrays.sort() 决定，为 O(n log n)
  
• ​空间复杂度​：O(k)，用于存储结果的列表
  

大顶堆法（推荐）

维护一个大小为k的大顶堆​（Max-Heap），堆顶是当前k个数中的最大值。遍历数组，如果当前数比堆顶小，则替换堆顶并调整堆
这⾥不展开最⼤堆和最⼩堆的具体讲解，什么是最⼤堆/最⼩堆呢？

• ⼤/⼩堆树是完全⼆叉树
  
• ⼤/⼩堆树的每⼀个节点不⼩于/不⼤于其孩⼦节点。
  

1. public ArrayList<Integer> GetLeastNumbers_Solution(int[] input, int k) {
2.     ArrayList<Integer> result = new ArrayList<>();
3.     if (input == null || k <= 0 || k > input.length) {
4.         return result;
5.     }
6.     // 创建一个大顶堆，使用自定义比较器实现降序排列
7.     PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a);
8.     for (int num : input) {
9.         if (maxHeap.size() < k) {
10.             maxHeap.offer(num); // 堆未满，直接加入
11.         } else if (num < maxHeap.peek()) { // 当前数比堆顶最大值小
12.             maxHeap.poll(); // 移除堆顶最大值
13.             maxHeap.offer(num); // 将当前数加入堆
14.         }
15.     }
16.     result.addAll(maxHeap);
17.     return result;
18. }

复制代码

• 时间复杂度​：O(n log k)。每次插入或删除堆的操作需要 O(log k) 时间，共需进行 n 次这样的操作
  
• ​空间复杂度​：O(k)，堆的大小
  

堆这种数据结构适合处理海量数据​（数据无法一次性装入内存），或者当 ​k 远小于 n​ 时非常高效。
大数据问题处理面试题：https://www.seven97.top/interview/intelligence-massivedata/massivedataprocessing.html
快速选择法（效率最优）

基于快速排序的 ​partition​ 操作。每次随机选择一个基准元素（pivot），将数组划分为比基准小和比基准大的两部分。根据基准的位置与k的关系，决定继续划分哪一部分
[code]public ArrayList GetLeastNumbers_Solution(int[] input, int k) {    ArrayList result = new ArrayList();    if (input == null || k  input.length) {        return result;    }    quickSelect(input, 0, input.length - 1, k);    for (int i = 0; i < k; i++) {        result.add(input);    }    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);    }}// 分区操作，将小于基准的数放在左边，大于基准的数放在右边，返回基准的最终位置private int partition(int[] arr, int left, int right) {    // 随机选择基准，避免最坏情况    int randomIndex = new Random().nextInt(right - left + 1) + left;    swap(arr, left, randomIndex);    int pivot = arr[left];    int i = left, j = right;    while (i < j) {        while (i < j && arr[j] >= pivot) j--;        while (i < j && arr