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.
解题思路：最简单的，我们可以选择将数组排序，然后返回第n-k项。另一种方法，我将数组以中间的数大小m为基准将数组分为左右两个数组，左数组小于m,右数组大于m；若右数组的大小q仍然大于k,则继续对右数组进行划分；当右数组大小等于k时，则该数组最小值即为所求，若右数组大小等于k-1,则划分数m即为所求；若右数组小于k，则将k = k - q -1；对左数组进行划分。
解答：
class Solution { public: int findKthLargest(vector<int>& nums, int k) { int num; find(nums,k,num); return num; } private: void find(vector<int>& nums,int k,int& num){ vector<int> a,b; int n = nums.size(); int r = n / 2; int m = nums[r]; nums[r] = nums[0]; nums[0] = m; for(int i = 1;i < n; i ++){ if(nums[i] > m){ b.push_back(nums[i]); } else{ a.push_back(nums[i]); } } int q = b.size(); int w = a.size(); if(q > k){ find(b,k,num); } else if(q == k){ int e = b[0]; for(int i= 0;i < q;i ++){ if(b[i] < e){ e = b[i]; } } num = e; } else if(q == k -1){ num = m; } else{ k = k - q -1; if(w == k){ int e = a[0]; for(int i= 0;i < w;i ++){ if(a[i] < e){ e = a[i]; } } num = e; } else{ find(a,k,num); } } } };
