215. 数组中的第K个最大元素

思路1：小顶堆

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {

        priority_queue<int,vector<int>, greater<int>> q;

        for(int i=0;i<nums.size();i++)
        {
            if(q.size()<k)
            {
                q.push(nums[i]);
            }
            else
            {
                if(nums[i]>q.top())
                {
                    q.pop();
                    q.push(nums[i]);
                }
            }

        }

        return q.top();
    }
};

思路2：快速选择
快排的基础上改进

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {

        int N=nums.size();
        int target=k-1; //第k大就是N-k小
        int l=0,r=N-1;

        while(l<=r)
        {
            int mid=partition(nums,l,r);
            if(mid==target)
                return nums[mid];
            else if(mid<target)
                l=mid+1;
            else
                r=mid-1;
        }
        return -1;    
    }

    int partition(vector<int>& nums, int left, int right)
    {

        int pivot=nums[left];

        while(left<right)
        {
           while(nums[right]<pivot && left<right){ right--;}
            nums[left]=nums[right];
        

           while(nums[left]>=pivot && left<right){left++;}
            nums[right]=nums[left];    

        }
        //cout<<left<<endl;

        nums[left]=pivot;
        
        return left;

    }
};