Description:
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.
Note:
You may assume k is always valid, 1 <= k <= array's length.
Example:
Given [3,2,1,5,6,4] and k = 2, return 5.
Link:
https://leetcode.com/problems/kth-largest-element-in-an-array/#/description
解题方法：
解法1：
直接用sort函数排序，再输出对应的数即可。方法比较粗暴，但是也能AC。
解法2：
使用了快速排序的思想，快速排序中有一个步骤叫partition，因为求第k大的数其实是求整个数组排序以后一个固定位置的数（nums.size() - k这个位置，下面用k来代替这个index）：
partition的实质是在进行了该操作以后，该数组在pivot之前的数一定不大于（或者不小于）pivot，在pivot之后的数一定不小于（或者不大于）pivot。也就是说在以后的排序中，这个pivot的位置上的元素是不会变的（哪怕变了也是一样的数）。这就找到了一个比快速排序更快捷的方法（worst case依然和quick sort一样），
1、当我们需要求这个数组在排序以后在k位置上的数，如果k正好在一次partition后pivot的这个位置上，可以直接返回这个数。
2、否则在包含k的这个范围内不断进行partition，直到出现1的情况。
3、当快速排序范围缩小到一个数的时候，其实这个数已经是被排序好的，那么直接返回就可以了。
然后需要确认另一个问题，partition以后，我们怎么能得到这个pivot的位置：
假设在一次partition中，左边的index设为left，右边的设为right，partition完成以后pivot的index变成了p。那么在这次partition完成以后可能会出现三种情况（暂且先不管k相对于他们的位置）：
1、数组nums分布情况为: start..... right, left, ... p ...end
2、数组nums分布情况为: start..... p, ... right, left ...end
3、数组nums分布情况为: start..... right, p, left, ...end
然后再来分析k与他们的分布关系：
当start <= k =< right时，此时不用管p在哪，直接对start~right这部分继续做partition。
当left < k <= end时，同上。
当k不在这两个范围内，说明right和left并不是连续的，也就是中间必然只有一个p，也就是说k == p，所以此时直接返回nums[k]就可以了。
Time Complexity：
可能是O(N)，但是worst case依然是O(N^2)。·
完整代码：
int findKthLargest(vector<int>& nums, int k)
{
return helper(nums, 0, nums.size() - 1, nums.size() - k);
}
int helper(vector<int>& nums, int start, int end, int k)
{
if(start == end)
return nums[start];
int left = start, right = end;
int mid = nums[left + (right - left)/2];
while(left <= right)
{
while(nums[left] < mid && left <= right)
left++;
while(nums[right] > mid && left <= right)
right--;
if(left <= right)
{
int temp = nums[left];
nums[left] = nums[right];
nums[right] = temp;
left++;
right--;
}
}
if(right >= k && start <= k)
return helper(nums, start, right, k);
if(left <= k && end >= k)
return helper(nums, left, end, k);
return nums[k];
}
