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
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.
You may assume k is always valid, 1 ≤ k ≤ array's length.
class Solution { public: int partition(vector<int>& nums, int start, int end, int k) { int pivot = nums[k]; swap(nums[end], nums[k]); int storedIndex = start; for(int i=start;i<=end-1;i++) { if(nums[i]>pivot) { swap(nums[i], nums[storedIndex]); storedIndex ++; } } swap(nums[end], nums[storedIndex]); return storedIndex; } int findKthLargest(vector<int>& nums, int k) { int end = nums.size()-1; if(end<0) return 0; int start = 0; k--; int ret = partition(nums, start, end, k); while(k != ret) { if(ret < k) ret = partition(nums, ret+1, end, k); else ret = partition(nums, start, ret-1, k); } return nums[k]; } };