本文共 2373 字，大约阅读时间需要 7 分钟。

• 过程：向小根堆中插入k个数，遍历剩下的n-k个数，当前数比堆顶大时，交换他们的值。
• 这样遍历完，堆顶是小根堆k个数中最小的，且比剩余的n-k的数都大，因此堆顶即为所求；此外，小根堆中所有的数是整个数组的前k大，堆顶就是第k大

代码如下（Leetcode 215）：

class Solution {   public:    int findKthLargest(vector
   
    & nums, int k) {           priority_queue
    
     
      ,greater
      
       > q;        int i=0;        for(;i
       
        q.top()){                   q.pop();                q.push(nums[i]);            }        return q.top();    }};
       
      
     
    
   

运行结果：

2. 思路2:基于快排思想（partition）

• partition过程（升序）：

1. 找当前arr最左边作为基准ref
2. 循环条件：left < right

• 右➡️左：找到比ref小的，放在左边
• 左➡️右：找到比ref大的，放在右边

3. 当left == right时结束循环，这个坐标就是ref应该在的index

int partition(vector
   
    & arr,int l,int r){       int ref = arr[l];    while(l
    
     =ref)            r--;        arr[l]=arr[r];        while(l
    
   

回到此题：

• 首先，不是快速排序，而是基于快速排序中的partition思想。快速排序对index左右都进行排序，每个子问题都要解决，本题目只解决一个子问题即可。
• 找第K大的，因此是降序，相应的改一下partition中的判断条件即可，过程如下：

1. 对最左数作为基准ref进行partition，得到该ref应在的index
2. left < right 时进行循环：

• 若index < K-1 : 说明第 K 大在右边，left = index + 1，继续partition
• 若index > K-1：说明第 K 大在左边，right = index -1，继续partition

3. left == right 时第K个数即为第K大

代码如下（牛客NC88）：

class Finder {   public:    int findKth(vector
   
     a, int n, int K) {           int left=0,right=n-1;        while(left