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.
要从一个数组中找出第k大的数。
难度：Medium
一种简单的思路是利用归并排序对数组进行排序以后，返回下标为K-1的元素，但是这种算法的时间复杂度为O（nlogn），实际上这道题还有更快的解法。
解题思路：
参考快排的思想，将数组划分成两个区域。首先随机从当前区域(开始下标记为start,最后一个元素的下标记为end)选取一个元素作为pivot（我的做法是选取当前划分好的区域中的第一个元素），参考快排的做法，把比pivot小的元素都放到pivot之前，把比pivot大的元素都放在它之后，这样就可以分出比pivot小的区域和比pivot大的区域。 比较这样一轮简单的划分后，计算比pivot大的元素个数end-i,其中i是划分以后pivot新位置的下标,如果end-i=k-1，就说明恰好有k-1个元素比pivot还要大，那么pivot就是要求的第K大的元素 。 如果K<end-i,则说明所要找的元素在pivot右侧，仍然要找右侧第K大的数。如果k>end-i,则所要找的元素在pivot左侧区域，由于包括pivot在内，已经有end-i+1个元素比第K大的元素大了，那么在左侧区域需要找到第K-(end-i+1)大的元素。
这种算法利用了分治的思想，不断把问题的规模缩小。不过它也有快排一样的缺点，就是如果数组一开始已经有序或者大部分元素已经按序排列，则时间复杂度会大大增加，最坏情况下时间复杂度为O（n^2）。
一般情况下，我们可以认为T（n）=T(n/2)+O(n),时间复杂度为O（n）,与归并排序以后再找到K大的数相比，效率大大提高了。
class Solution { public: int helper(vector<int>&nums,int k,int start,int end) { int pivot=nums[start]; int i=start,j=end; bool flag=0; while(i!=j) { while(nums[j]>=pivot && i<j) { j--; } while(nums[i]<=pivot && i<j) { i++; } if(i<j) { int t; t=nums[i]; nums[i]=nums[j]; nums[j]=t; } } int t; t=nums[start]; nums[start]=nums[i]; nums[i]=t; int m=i+1; if(end-i+1==k) { return nums[i]; } else if(end-i<k) { return helper(nums,k-(end-i+1),start,i-1); } else { return helper(nums,k,i+1,end); } } int findKthLargest(vector<int> & nums,int k ) { int size=nums.size(); return helper(nums,k,0,nums.size()-1); } };
注：参考《算法导论》 作者：Thomas H.Cormen、Charles E.Leiserson
