🚩传送门：牛客题目

题目

给定一个数组，找出其中最小的K个数。例如数组元素是4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4。

  • 0 <= k <= input.length <= 10000
  • 0 <= input[i] <= 10000

示例 1:

输入：[4,5,1,6,2,7,3,8],4 返回值：[1,2,3,4] 说明：返回最小的 4 个数即可，返回 [1,3,2,4] 也可以

示例 2:

输入：[1],0 返回值：[]

示例 3:

输入：[0,1,2,1,2],3 返回值：[0,1,1]

解题思路：排序

此解法，会被视作对面试官的挑衅行为！慎用！

对原数组从小到大排序后取出前 _k_ 个数即可。

复杂度分析

时间复杂度： 🍗[NC]119. 最小的 K 个数 【堆排、快排】 - 图1 ，其中 🍗[NC]119. 最小的 K 个数 【堆排、快排】 - 图2 是数组的长度。

算法的时间复杂度即排序的时间复杂度。

空间复杂度：🍗[NC]119. 最小的 K 个数 【堆排、快排】 - 图3 或者 🍗[NC]119. 最小的 K 个数 【堆排、快排】 - 图4

排序所需额外的空间复杂度由具体排序算e算e法决定。

整理代码

  1. class Solution {
  2.     public int[] getLeastNumbers(int[] arr, int k) {
  3.         int[] vec = new int[k];
  4.         Arrays.sort(arr);
  5.         for (int i = 0; i < k; ++i) {
  6.             vec[i] = arr[i];
  7.         }
  8.         return vec;
  9.     }e
  10. }

解题思路：冒泡排序

  • 最小就从右向左冒泡（右边比左边小就交换）
  • 最大就从左向右冒泡（左边比右边大就交换）

整理代码

  1. public class Solution {
  2.     public int[] getLeastNumbers(int[] arr, int k) {
  3.         //冒泡 K 次
  4.         for(int j=0;j<k;j++){
  5.             for(int i=arr.length-1;i>j;i--){
  6.                 if(arr[i]<arr[i-1]){
  7.                     int temp=arr[i];
  8.                     arr[i]=arr[i-1];
  9.                     arr[i-1]=temp;
  10.                 }
  11.             }
  12.         }
  13.         int[]res=new int[k];
  14.         System.arraycopy(arr, 0, res, 0, k);
  15.         return res;
  16.     }
  17. }

🚩解题思路：堆排序

🍗思路1：
我们用一个大根堆实时维护数组的前 k 小值。

  1. 首先将前 k 个数插入大根堆中
  2. 随后从第 k+1 个数开始遍历
    • 如果当前遍历到的数比大根堆的堆顶的数要小，就把堆顶的数弹出，再插入当前遍历到的数。
  3. 最后将大根堆里的数存入数组返回即可。

    🍗思路2： 当然也可以用小根堆，然后出堆，调整，用 k 次找出前最小的 k 个数 [ 参考堆排序的过程 ]

复杂度分析

时间复杂度： 🍗[NC]119. 最小的 K 个数 【堆排、快排】 - 图5 ，其中 🍗[NC]119. 最小的 K 个数 【堆排、快排】 - 图6 是数组的长度。

由于大根堆实时维护前 k 小值，所以插入删除都是 🍗[NC]119. 最小的 K 个数 【堆排、快排】 - 图7 的时间复杂度，最坏情况下数组里 n 个数都会插入，所以一共需要 🍗[NC]119. 最小的 K 个数 【堆排、快排】 - 图8 的时间复杂度。

空间复杂度：🍗[NC]119. 最小的 K 个数 【堆排、快排】 - 图9

因为大根堆里最多 k 个数。

整理代码

  1. class Solution {
  2.     public int[] getLeastNumbers(int[] arr, int k) {
  3.         int[] vec = new int[k];
  4.         if (k == 0) return vec; // 排除 0 的情况
  5.         //1.定义优先队列,内部结构是堆
  6.         PriorityQueue<Integer> queue = new PriorityQueue<Integer>(new Comparator<Integer>() {
  7.             public int compare(Integer num1, Integer num2) {
  8.                 return num2 - num1;
  9.             }
  10.         });
  11.         //2.将前k个数入大根堆
  12.         for (int i = 0; i < k; ++i) {
  13.             queue.offer(arr[i]);
  14.         }
  15.         //3.遍历后面的n-k个数字,比大根堆小的入堆
  16.         for (int i = k; i < arr.length; ++i) {
  17.             if (queue.peek() > arr[i]) {
  18.                 queue.poll();
  19.                 queue.offer(arr[i]);
  20.             }
  21.         }
  22.         //4.将堆中的k个数放入答案数组
  23.         for (int i = 0; i < k; ++i) {
  24.             vec[i] = queue.poll();
  25.         }
  26.         return vec;
  27.     }
  28. }

🚩解题思路：快速排序

我们可以借鉴快速排序的思想。我们知道快排的划分函数每次执行完后都能将数组分成两个部分，小于等于分界值 pivot 的元素的都会被放到数组的左边，大于的都会被放到数组的右边，然后返回分界值的下标。与快速排序不同的是，快速排序会根据分界值的下标递归处理划分的两侧，而这里我们只处理划分的一边。

我们定义函数 randomized_selected(arr, l, r, k) 表示划分数组 arr 的 [l,r] 部分，使前 k 小的数在数组的左侧，在函数里我们调用快排的划分函数，假设划分函数返回的下标是 pos（表示分界值 pivot 最终在数组中的位置），即 pivot 是数组中第 pos - l + 1 小的数，那么一共会有三种情况：

  • 如果 pos - l + 1 == k，表示 pivot 就是第 k 小的数，直接返回即可；
  • 如果 pos - l + 1 < k，表示第 k 小的数在 pivot 的右侧
    • 因此递归调用 randomized_selected(arr, pos + 1, r, k - (pos - l + 1))；
  • 如果 pos - l + 1 > k，表示第 k 小的数在 pivot 的左侧
    • 因此递归调用 randomized_selected(arr, l, pos - 1, k)。

函数递归入口为 randomized_selected(arr, 0, arr.length - 1, k)。在函数返回后，将前 k 个数放入答案数组返回即可。

复杂度分析

时间复杂度： 🍗[NC]119. 最小的 K 个数 【堆排、快排】 - 图10 ，其中 🍗[NC]119. 最小的 K 个数 【堆排、快排】 - 图11 是数组的长度。由于证明过程很繁琐，所以不在这里展开讲。

  1.   - 最坏情况下的时间复杂度为  ![](https://cdn.nlark.com/yuque/__latex/56520ff852bbdb26d3f8f6e0923fd03e.svg#card=math&code=%5Csmall%20O%28n%5E2%29&id=dQmjc) ，情况最差时，每次的划分点都是最大值或最小值。

空间复杂度：🍗[NC]119. 最小的 K 个数 【堆排、快排】 - 图12 

  1.   - 递归调用的期望深度为 ![](https://cdn.nlark.com/yuque/__latex/e5bd5cdd935a4f148f3fc7cb2148b873.svg#card=math&code=%5Csmall%20O%28%5Clog_2n%29&height=20&id=t7XPs) ，每层需要的空间为 ![](https://cdn.nlark.com/yuque/__latex/2744619fca12271057dcb91f0e316d55.svg#card=math&code=%5Csmall%20O%281%29&height=20&id=vgQul) ，只有常数个变量。
  2.   - 最坏情况下的空间复杂度为  ![](https://cdn.nlark.com/yuque/__latex/bf7c2e3ac858e1c3496fd2f47a300139.svg#card=math&code=%5Csmall%20O%28n%29&height=20&id=yR3FT) 。最坏情况下需要划分 **n** 次，即 `randomized_selected` 函数递归调用最深 **n−1** 层，而每层由于需要  ![](https://cdn.nlark.com/yuque/__latex/2744619fca12271057dcb91f0e316d55.svg#card=math&code=%5Csmall%20O%281%29&height=20&id=EWCBF)  的空间，所以一共需要  ![](https://cdn.nlark.com/yuque/__latex/bf7c2e3ac858e1c3496fd2f47a300139.svg#card=math&code=%5Csmall%20O%28n%29&height=20&id=pvZiv)  的空间复杂度。

整理代码

  1. class Solution {
  2.     //#外部调用函数
  3.     public int[] getLeastNumbers(int[] arr, int k) {
  4.         //通过此函数求出前K小值,集中于arr数组的前k项
  5.         randomizedSelected(arr, 0, arr.length - 1, k);
  6.         int[] vec = new int[k];
  7.         //将arr数组的前k项放入vec数组
  8.         for (int i = 0; i < k; ++i) {
  9.             vec[i] = arr[i];
  10.         }
  11.         return vec;
  12.     }
  13.     //#区间划分函数
  14.     private void randomizedSelected(int[] arr, int l, int r, int k) {
  15.         if (l >= r) {
  16.             return;
  17.         }
  18.         //1.随机获得一个基准,并通过基准将数组划分成两个区间,并获得基准的下标
  19.         int pos = randomizedPartition(arr, l, r);
  20.         int num = pos - l + 1;
  21.         //2.通过下标来判断符合答案还是去左侧还是右侧
  22.         if (k == num) {
  23.             return;
  24.         } else if (k < num) {
  25.             randomizedSelected(arr, l, pos - 1, k);
  26.         } else {
  27.             //[0-pos]是前pos+1个最小值,因此需要在[pos+1,r]的右侧找出剩下的k-num个最小值
  28.             randomizedSelected(arr, pos + 1, r, k - num);    
  29.         }
  30.     }
  32.     //#随机从数组中选出一个基准
  33.     private int randomizedPartition(int[] nums, int l, int r) {
  34.         int i = new Random().nextInt(r - l + 1) + l;
  35.         swap(nums, r, i);
  36.         return partition(nums, l, r);
  37.     }
  39.     //#单for循环式的快排基准划分
  40.     private int partition(int[] nums, int l, int r) {
  41.         int pivot = nums[r];
  42.         int i = l - 1;
  43.         for (int j = l; j <= r - 1; ++j) {
  44.             if (nums[j] <= pivot) {
  45.                 i = i + 1;
  46.                 swap(nums, i, j);
  47.             }
  48.         }
  49.         swap(nums, i + 1, r);
  50.         return i + 1;
  51.     }
  53.     //#交换函数
  54.     private void swap(int[] nums, int i, int j) {
  55.         int temp = nums[i];
  56.         nums[i] = nums[j];
  57.         nums[j] = temp;
  58.     }
  59. }