LeetCode215 数组中的第k最大元素

在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

直接用快速排序的partition函数，可以在O(n)时间内解决。或者使用最大堆，时间复杂度为O(nlogn)。

 1 class Solution {
 2 public:
 3     int findKthLargest(vector<int>& nums, int k) {
 4         int n=nums.size();
 5         return partition(nums,0,n-1,n-k);
 6     }
 7 
 8     int partition(vector<int>& nums,int left, int right, int k){
 9         if(left==right)
10             return nums[left];
11         int standard=nums[left];
12         int orileft=left,oriright=right;
13         while(left<right){
14             while(left<right && nums[right]>=standard)
15                 --right;
16             if(left<right)
17                 nums[left]=nums[right];
18             
19             while(left<right && nums[left]<standard)
20                 ++left;
21             if(left<right)
22                 nums[right]=nums[left];
23         }
24         nums[left]=standard;
25         cout<<nums[left]<<endl<<left<<endl;
26         if(left==k)
27             return standard;
28         else if(left>k)
29             return partition(nums,orileft,left-1,k);
30         else 
31             return partition(nums,left+1,oriright,k);
32     }
33 };