class Solution {
public:
    static bool cmp(int& a,int& b)
    {
        return a>b;
    } 
    int findKthLargest(vector<int>& nums, int k) 
    {
        priority_queue<int,vector<int>,decltype(&cmp)> que_temp(cmp);
        for(auto& temp:nums)
        {
            if(que_temp.size() == k)
            {
                if(temp>que_temp.top())
                {
                    que_temp.pop();
                    que_temp.emplace(temp);
                }
            }
            else
            que_temp.emplace(temp);
        }
        return que_temp.top();
    }
};

class Solution {
public:
    int quickselect(vector<int>& nums,int begin,int end,int k)
    {
        int selected = rand()%(end-begin+1)+begin;
        swap(nums[selected],nums[begin]);
        int pivot = nums[begin];
        int index = begin;
        for(int i = begin+1 ; i <= end ; i++)
        {
            if(nums[i] > pivot)
            {
                swap(nums[i],nums[index+1]);
                index++;
            }
        }
        swap(nums[begin],nums[index]);
        if(index+1<k)
        {
            return quickselect(nums,index+1,end,k);
        }
        else if(index+1>k)
        {
            return quickselect(nums,begin,index-1,k);
        }
        else
        {
            return nums[index];
        }
    }
    int findKthLargest(vector<int>& nums, int k) 
    {
        return quickselect(nums,0,nums.size()-1,k);
    }
};