Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.
For example,
Given [3,2,1,5,6,4] and k = 2, return 5.
Note:
You may assume k is always valid, 1 ≤ k ≤ array‘s length.
方法一：利用快速排序的partition的部分，这样每次都能知道第一个数的左边有多少个数，与k比较大小，分类讨论。注意点，while中是小于号，注意与二分查找的不同，整个执行结束low==high。
class Solution { public: int helper(vector<int>& nums, int k, int begin, int end){ int temp=nums[begin]; int origBegin=begin,origEnd=end; while(begin<end){ while(begin<end&&nums[end]<=temp)end--; nums[begin]=nums[end]; while(begin<end&&nums[begin]>=temp)begin++; nums[end]=nums[begin]; } nums[begin]=temp; //cout<<begin<<‘ ‘<<end<<endl; if(begin-origBegin+1==k)return nums[begin]; else if(begin-origBegin+1<k)return helper(nums,k-begin-1+origBegin,begin+1,origEnd); else return helper(nums,k,origBegin,end); } int findKthLargest(vector<int>& nums, int k) { return helper(nums,k,0,nums.size()-1); } };
方法二：利用优先队列，先塞进去k个数，碰到比最小值更大的就更新，最后的队列首部肯定就是要求的第k大值。
class Solution { public: int findKthLargest(vector<int>& nums, int k) { priority_queue<int, vector<int>, greater<int>> minHeap; for(int i = 0; i<nums.size(); i++){ if(i<k) minHeap.push(nums[i]); else{ int topv = minHeap.top(); if(topv < nums[i]) {minHeap.pop(); minHeap.push(nums[i]);} } } return minHeap.top(); } };
方法三：利用stl的nth_element.
class Solution { public: int findKthLargest(vector<int>& nums, int k) { int n = nums.size(); nth_element(nums.begin(), nums.begin() + n - k, nums.end()); return nums[n - k]; } };
215. Kth Largest Element in an Array
原文：http://www.cnblogs.com/tsunami-lj/p/7631864.html