🚩传送门：牛客题目

题目

有一个整数数组，请你根据快速排序的思路，找出数组中第 [NC]88. 寻找第 K 大 【大根堆、小根堆的compare 准则写法】 - 图1 大的数。给定一个整数数组 [NC]88. 寻找第 K 大 【大根堆、小根堆的compare 准则写法】 - 图2 ,同时给定它的大小 [NC]88. 寻找第 K 大 【大根堆、小根堆的compare 准则写法】 - 图3 和要找的 [NC]88. 寻找第 K 大 【大根堆、小根堆的compare 准则写法】 - 图4 ，请返回第 [NC]88. 寻找第 K 大 【大根堆、小根堆的compare 准则写法】 - 图5 大的数(包括重复的元素，不用去重)，保证答案存在。要求时间复杂度 [NC]88. 寻找第 K 大 【大根堆、小根堆的compare 准则写法】 - 图6 。

示例1

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

示例2

输入：[10,10,9,9,8,7,5,6,4,3,4,2],12,3 返回值：9 说明：去重后的第3大是8，但本题要求包含重复的元素，不用去重，所以输出9

🚩解题思路：堆排序

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

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

复杂度分析

时间复杂度： [NC]88. 寻找第 K 大 【大根堆、小根堆的compare 准则写法】 - 图7 ，其中 [NC]88. 寻找第 K 大 【大根堆、小根堆的compare 准则写法】 - 图8 是数组的长度。

由于大根堆实时维护前 k 小值，所以插入删除都是 [NC]88. 寻找第 K 大 【大根堆、小根堆的compare 准则写法】 - 图9 的时间复杂度，最坏情况下数组里 n 个数都会插入，所以一共需要 [NC]88. 寻找第 K 大 【大根堆、小根堆的compare 准则写法】 - 图10 的时间复杂度。

空间复杂度：[NC]88. 寻找第 K 大 【大根堆、小根堆的compare 准则写法】 - 图11

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

整理代码

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

🚩解题思路：快速排序

我们可以借鉴快速排序的思想。我们知道快排的划分函数每次执行完后都能将数组分成两个部分，小于等于分界值 pivot 的元素的都会被放到数组的左边，大于的都会被放到数组的右边，然后返回分界值的下标。

这里做出修改：为了迎合第 K 大倒序的求解要求，大于等于分界值 **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]88. 寻找第 K 大 【大根堆、小根堆的compare 准则写法】 - 图12 ，其中 [NC]88. 寻找第 K 大 【大根堆、小根堆的compare 准则写法】 - 图13 是数组的长度。由于证明过程很繁琐，所以不在这里展开讲。

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

空间复杂度：[NC]88. 寻找第 K 大 【大根堆、小根堆的compare 准则写法】 - 图14 

  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 {
  3.     //#外部调用函数
  4.     public static int findKth(int[] a, int n, int K) {
  5.         //通过此函数求出前K小值,集中于arr数组的前k项
  6.         randomizedSelected(a, 0, n - 1, K);
  7.         //在前 k 项中找出最大值
  8.         int min =a[0];
  9.         for(int i=1;i<K;i++){
  10.             if(a[i]<min) min=a[i];
  11.         }
  12.         return min;
  13.     }
  15.     //#区间划分函数
  16.     private static void randomizedSelected(int[] arr, int l, int r, int k) {
  17.         if (l >= r) {
  18.             return;
  19.         }
  20.         //1.随机获得一个基准,并通过基准将数组划分成两个区间,并获得基准的下标
  21.         int pos = randomizedPartition(arr, l, r);
  22.         int num = pos - l + 1;
  23.         //2.通过下标来判断符合答案还是去左侧还是右侧
  24.         if (k == num) {
  25.             return;
  26.         } else if (k < num) {
  27.             randomizedSelected(arr, l, pos - 1, k);
  28.         } else {
  29.             //[0-pos]是前pos+1个最小值,因此需要在[pos+1,r]的右侧找出剩下的k-num个最小值
  30.             randomizedSelected(arr, pos + 1, r, k - num);
  31.         }
  32.     }
  34.     //#随机从数组中选出一个基准
  35.     private static int randomizedPartition(int[] nums, int l, int r) {
  36.         int i = new Random().nextInt(r - l + 1) + l;
  37.         swap(nums, r, i);
  38.         return partition(nums, l, r);
  39.     }
  41.     //#单for循环式的快排基准划分
  42.     private static int partition(int[] nums, int l, int r) {
  43.         int pivot = nums[r];
  44.         int i = l - 1;
  45.         for (int j = l; j <= r - 1; ++j) {
  46.             if (nums[j] > pivot) {
  47.                 i = i + 1;
  48.                 swap(nums, i, j);
  49.             }
  50.         }
  51.         swap(nums, i + 1, r);
  52.         return i + 1;
  53.     }
  55.     //#交换函数
  56.     private static void swap(int[] nums, int i, int j) {
  57.         int temp = nums[i];
  58.         nums[i] = nums[j];
  59.         nums[j] = temp;
  60.     }
  62.     public static void main(String[] args) {
  63.         int[] arr=new int[]{10,10,9,9,8,7,5,6,4,3,4,2};
  64.         System.out.println(findKth(arr,12,3));
  65.         Arrays.stream(arr).sorted();
  66.         for(int num:arr){
  67.             System.out.print(num+"  ");
  68.         }
  69.     }
  70. }