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.
Example 1:
Input: [3,2,1,5,6,4] and k = 2
Output: 5
Example 2:
Input: [3,2,3,1,2,4,5,5,6] and k = 4
Output: 4
题目
找数组里第K大的元素，这里指的是排好序后，从后往前数第k个数，是包含重复元素的。
思路
快排改造：
如果是有序数组，我们一下就能找到第k大的元素，但是所给数组无序，我们就需要先排序，但是又没必要全部排好序，所以可以依照快排思想，稍作改造，顺便复习一下快排。
快排思想：
- 我们在数组里选择一个参考元素，这个参考元素一般选第一个元素，或者随机选一个把它和第一个元素换一下位置。
- 两个指针分别从头尾遍历数组，如果头指针所指元素小于参考元素就继续往后走，尾指针所指元素大于参考元素就继续往前走，若不满足，则停下来，把两个指针元素交换位置，然后继续遍历，直到两指针相遇。
- 遍历一次下来，数组左边的元素都小于等于参考元素，右边的元素都大于等于参考元素，此时再把参考元素（第一个）和两指针相遇位置的元素互换。就完成了第一次快排。
此时数组为：[小于等于参考元素,...,参考元素,...,大于等于参考元素]。 - 分别再对前半段数组和后半段数组重复上述123步骤，最后整个数组就排好了。
针对本题目，我们排完一次，可以判断一下指针的位置:
- 即数组右半边若刚好有k-1个元素，那么中间这个元素就是第k大的元素；
- 若数组右半边的元素数量<k-1个元素，说明第k大的元素在数组左半边；
- 若数组右半边的元素数量>k-1个元素，说明第k大的元素在数组右半边；
- 最后，依据上述不同情况，在特定区间递归寻找即可；
代码实现如下：
代码
public int findKthLargest(int[] nums, int k) {
int l=0;
int r=nums.length-1;
return partition(l,r,nums,k);
}
private int partition(int start, int end, int[] nums,int k) {//快排分区
// int random =(int)(Math.random()*(r-l+1)+l);
// swap(nums,l,random);//先让第一个元素随机交换位置
int i=start;
int j=end;
int v=nums[i];//这里我们就按照第一个元素划分
while (i<j) {
while (i<j&&nums[j]>=v) {//先让j往前走，遇到小于v的停下来。这里一定要先让j走！！
//因为i是从第一个元素开始的，而第一个元素的值已经存在v里了。所以先让j走，去覆盖i，没事。
j--;
}
if(i<j)
nums[i++]=nums[j];//与i交换，同时i往前走
while (i<j&&nums[i]<=v) {//此时i再往后走,遇到大于v的就和j交换，此时j是指向从后往前第一个小于v的数，而且是已经复制过去了，所以这个值是重复的。
i++;
}
if(i<j)
nums[j--]=nums[i];
//找到后交换位置
}
nums[i]=v;//最后一步，把参考元素和指针交换，一轮就分完了
if (k==end-j+1) {//从队尾到v一共k-1个元素的话，那么v就是第k大的元素
return v;
}else if (k<end-j+1) {//比v大的数已经超过k个了，所以第k大的数肯定在这里面
return partition(j+1, end, nums, k);
}else {//否则证明右边还没拍到第k大，所以在坐便继续找，这时注意我们在左边就是找（k-右边这么多元素）就够了
return partition(start, j-1, nums, k-(end-j+1));
}
}
