/*
 在未排序的数组中找到第 k 个最大的元素。请注意，
 你需要找的是数组排序后的第 k 个最大的元素，
 而不是第 k 个不同的元素。
 
 示例 1:
 
 输入: [3,2,1,5,6,4] 和 k = 2
 输出: 5
 示例 2:
 
 输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
 输出: 4
*/
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

class Solution {
public:
    int Partition(vector<int> &vec,int left,int right)
    {
        swap(vec[left],vec[rand()%(right-left+1)+left]);
        int v=vec[left];
        int i=left+1;
        int j=right;
        while(1)
        {
            while(i<=right && vec[i]<v) i++;
            while(j>=left && vec[j]>v)  j--;
            if(i>j)
                break;
            swap(vec[i],vec[j]);
        }
        swap(vec[left],vec[j]);
        return j;
    }
    int findKthLargest(vector<int>& nums, int k) {
        int left=0;
        int right=nums.size()-1;
        int target=nums.size()-k;
        while(1)
        {
            int index=Partition(nums,left,right);
            if(index==target)
                return nums[index];
            else if(index<target)
                left=index+1;
            else
                right=index-1;
        }
        
    }
    
    //利用小根堆的性质，维持堆中的元素个数始终为k，最有返回堆顶的元素
    int findKthLargest2(vector<int>& nums, int k) {
        
        priority_queue<int,vector<int>,greater<int> > p;
        
        for(int i=0;i<nums.size();i++)
        {
            p.push(nums[i]);
            if(p.size()>k)
            {
                p.pop();
            }
        }
        return p.top();
    }
    
    
};
int main()
{
    vector<int> vec{4,6,2,3,1,5,7,8};
    int k=2;
    cout<<Solution().findKthLargest2(vec, k);
}