写在前面

对于一个无序数组，求第 $K$ 个最大元素，最容易想到的就是排序，然后选择相应位置的元素；其中有些排序算法是可以提前终止的，比如快速排序、冒泡、交换排序等。

快速选择算法

依托于快排思想，只不过根据partition函数的返回值来确定是快排左侧还是右侧，还是直接返回答案。为了方便理解和取出元素，利用快排进行从大到小排序。

  • 整体思路和快速排序是一致的，只不过在确定好parttition的位置后，根据条件选择排序哪一边的。

  • 快速排序基本框架：

    • 对数组进行洗牌打乱、递归排序函数
    • 主要包含的函数：洗牌算法、交换函数、partition函数（最重要的部分）

    • partition函数最主要的就是维护一个区间，同时记住最后要和哪个元素进行交换，这与你选择的 pivot 位置很相关。

      class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
shuffle(nums); // 打乱
sort(nums,0,nums.size()-1,k);
return nums[k-1];
}
// 利用快速排序来选择出第K个大的元素，从大到小排列即可
// 左边都是小于 pivot 的，右边都是大于 pivot 的

void sort(vector<int>&nums,int lo,int hi,int k){
if(lo>=hi)
    return;
int p=partition(nums,lo,hi);
if(p==k-1)
    return;
else if(p>k-1)
    // 排序左边的
    sort(nums,lo,p-1,k);
else
    sort(nums,p+1,hi,k);
return;
}
    
// partition 函数: 返回的是索引值
int partition(vector<int>&nums,int lo,int hi){
int pivot=nums[lo];  // 选择末尾或者开头都可以
int i=lo+1,j=hi;
// 保证pivot左侧都是大于pivot的，右侧都是小于pivot的
while(i<=j){
// 终止条件是 nums[i] <= pivot
while(i<hi && nums[i]>pivot)
    i++;
// 终止条件是 nums[j] > pivot
while(j>lo && nums[j]<=pivot)
    j--;
if(i>=j)
    break;
swap(nums,i,j);
}
swap(nums,lo,j);
return j;
}

// shuffle函数：满足 N! 种情况
void shuffle(vector<int>&nums){
std::srand(std::time(nullptr));
for(int i=0;i<nums.size();i++){
    int rands=rand()%(nums.size()-i);  // 0到N-i-1之间
    swap(nums,i,i+rands);  // 与其及其后的某一个交换
    // 总的情况数为：N*(N-1)*...*1=N!
}
}

// 交换函数
void swap(vector<int>&nums,int i,int j){
int temp=nums[i];
nums[i]=nums[j];
nums[j]=temp;
return;
}
};

优先队列（最小堆）

利用C++中的内置容器，优先队列priority_queue<int>，遍历一遍nums，为了方便取出第 $K$ 个最大元素，采用最小堆，也就是降序的，同时始终维护队列中有 $K$ 个元素。

  • C++中的优先队列
    • priority_queue<int,vector<int>,cmp> var,指明数据类型int,存放数据的容器vector<int>(默认),以及优先级cmp。

  • 如何自己实现优先队列？

    • 图文详解二叉堆，实现优先级队列

      class Solution {
public:
struct cmp{
// 比较函数
bool operator()(const int& a,const int & b)const{
    // 降序排列：从小到大排序
    return a>b;
}
};
int findKthLargest(vector<int>& nums, int k) {
// 利用优先队列，注意c++中的默认是最大堆
// 因此需要cmp来设置为最小堆，这样才能取出队首的元素
priority_queue<int,vector<int>,cmp> Q;
for(auto id:nums)
{
    Q.push(id);
    if(Q.size()>k)
        Q.pop();
}
return Q.top();
}
};

$\cdots$ end $\cdots$