215. Kth Largest Element in an Array(第k大的数）-蒲公英云

215. Kth Largest Element in an Array(第k大的数）

**题目：**在未排序的数组中找到第k个最大元素。请注意，它是排序顺序中第k个最大的元素，而不是第k个不同的元素。

思路：这个题目的思路不不止一个：
思路1（最快的）：采用stl的 nth_element()函数来进行选出第k大的数字。实现细节：参数一共有四个 nth_element(nums.begin(), nums.begin() + k - 1, nums.end(), greater()); 然后就返回nums[k-1]。
**实现细节：**不断用 median-of-3-partitioning (三点中值为中枢分割）将整个序列分割为更小的左右序列。如果nth 迭代器落到左边，左边再分割，直到分割后的子序列长度不大于3.然后插入排序。

思路2，利用堆的特性，priority_queue 容器来弹出k-1个数。
思路3：快速排序，设置哨兵，然后从两边往中间走，直到哨兵处于第k个，获得，注意一开始的 l 与 r要可以相等，否则到了最后的l==r时，会直接跳过

代码1：nth_element()

int findKthLargest(vector<int>& nums, int k) { 
        nth_element(nums.begin(), nums.begin() + k - 1, nums.end(), greater<int>());
        return nums[k - 1];
    }

代码2：priority_queue

int findKthLargest(vector<int>& nums, int k){ 
 priority_queue<int> heap(nums.begin(), nums.end());
        for(int i=0;i<k-1;++i)
            heap.pop();
        return heap.top();
        }

代码3：快速排序

class Solution { 
 int findKthLargest(vector<int>& nums, int k){ 
        if(k>nums.size())
            return -1;
        findres(nums, k,0, nums.size()-1);
        return res;
    }
        void findres(vector<int>& nums, int k ,int l,int r){ 
            if(l<=r){ 
                int low=l,high=r;
                int sentry=nums[l];
                while(low<high){ 
                    while(low<high && nums[high]<sentry)
                        high--;
                    if(low<high)
                        nums[low++]=nums[high]; //第一个小于sentry的
                    while(low<high && nums[low]>sentry)
                        low++;
                    if(low<high)
                        nums[high--]=nums[low];
                }
                //找到对应的位置了，但是low还没有赋值
                nums[low]=sentry;
                if(low+1==k)
                   {  res=nums[low];
                    return ;}
                else if(low+1 >k)
                  findres(nums, k,l,low-1);
                else
                  findres(nums,k,low+1,r);
            }
            return ;
        }
private:
    int res;
    };