题目描述
在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
示例 1:
输入: [3,2,1,5,6,4] 和 k = 2
输出: 5
示例 2:
输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 4
说明:
你可以假设 k 总是有效的，且 1 ≤ k ≤ 数组的长度。
这道题 想要考我们什么咧？
其实这道题是想考一个快速排序。
快速排序的原理就是 每一次能确定一个数的位置。
然后再对该数左右两边的数组用同样的方法 分治排好。
所以其实这道题的思路也很简单，首先就得对数组进行一次快速排序，然后确定一个数的位置，然后再根据我们要求的是第几个不同的元素，判断去排左边或者右边。
比如有6个元素，要求的是第五个，那么假设第一次排好的位置是3，就只需要找右边的，不要找左边的。
不过先熟悉一下快速排序吧，这个看我之前写过的快速排序算法。
不过那里讲得有点基础，是从最原始开始推起，假设已经有点印象了，非常熟练了，其实是可以十分钟就写出来了，只要记住几个原则手写快速排序。
- 快速排序的整体思路就是每一次找出一个数的位置
- 然后再对该数位置左右两边运用同样的分治方法排好序。
- 那么如何找出一个数的位置呢？就是用两个指针，两个while循环，循环遍历就可以了，其实记住之后挺简单的。
void quick_sort(int num[],int begin,int end) {
int left = begin;
int right = end;
if (end < begin) return;//递归出口这里要注意！是end<begin！！！ 就这里需要注意一下！
int key = num[left];
while (left < right) {
while (left < right && num[right] > key) {
right--;
}
num[left] =num[right];//这边记得是数组两边交换
left++;
while (left < right && num[left] < key) {
left++;
}
num[right] = num[left];//这边记得是数组两边交换
right--;
}
num[left] = key; //最后遍历循环一遍后，就把left==right的地方插上原本的数，就得到该数的位置了。
// System.out.println(num[left]);
quick_sort(num, begin, left - 1);
quick_sort(num, right + 1, end);
}
好了，然后讲一下关于这道题的快速排序改装法，其实就是改装一下就可以了。
比如说要找第2个最大的元素，那么如果数组有6个数的话，其实也就是要找升序排序第4个数，也就是下标为3的数，所以要找第k个最大的数，我们可先算出n=nums.length-1-k算出下标
然后最主要就是在最后递归那里，因为我们已经得到一个数的位置了，现在判断，
- 若该位置，就是所求的n，即返回该数
- 若所求的在该位置右边，则进行右循环即可
- 若所求的在该位置左边，则进行左循环即可
//最上面
int l=num.length-k;
注意这里的l 只需要减k，不用再减1，因为第一个位置最大，是从1开始，搞不懂建议写几个数推一下。
if(l==leftkey)return num[leftkey];
else if(l<leftkey)return sort22(num,begin,leftkey-1,k);
else if(l>leftkey)return sort22(num,rightkey+1,end,k);
return -1;