第K大的元素：三路快速排序算法思路
解题思路
这个题可以利用快速排序算法的隔断思想来解，我们快速排序找到的隔断（partition）在接下来的递归中都不再处理了，因此找到的隔断找到后在哪，排完序之后也是在找到的位置的，从而可以判断k与隔断的大小关系来快速得出第k大的元素在哪。首先同样的，确保第k大的数值在数组中能找到，然后第k大在数组中不好顺序表示，就直接转换成第k小的，例如第1大的可以转换成第length小的，然后因为我这边使用的三路快速排序算法（对全部一样的数值的数组有速度优势），需要传回两个值，Java不支持多变量返回，我就直接写在一个函数里了，首先是初始化好相关变量，约定好隔断：V，(l,tl)<V,[tl,i)=V,[i,tg]未处理,(tg,r)>V，然后遍历[l,r)，把相对应的元素放置到对应位置，最后处理隔断V，处理好之后就变成了[l,tl)<V, [tg,r)>V, [tl,tg) = V，这样，我们再判断k在哪个区间，如果是在等于V的区间，V是已经排好序了的，那就可以直接返回，在小于V的区间就调整r值后再次找隔断，同理大于V则调整l之后再调整，这样一步一步就能得到k处的元素值。
对三路快速排序算法不太了解的同学可以去了解一下，这边双路应该也是可以实现的。
代码
class Solution {
public int findKthLargest(int[] nums, int k) {
if (k > nums.length) { // 如果不存在
return -1;
}
// 输入的是找第k大的，转换成找第k小的
k = nums.length-k;
// 为分割做准备
Random random = new Random();
int l = 0, r = nums.length;
do {
// 获取随机隔断
int rd = random.nextInt(r - l) + l;
swap(nums, rd, l);
// 三路快速排序算法
// (l,tl)<V,[tl,i)=V,[i,tg]未处理,(tg,r)>V
int i = l + 1, tl = l + 1, tg = r - 1;
while (i <= tg) {
if (nums[l] > nums[i]) {// 小于V的部分
swap(nums, i, tl);
tl++;
i++;
} else if (nums[l] < nums[i]) {
swap(nums, i, tg);
tg--;
} else { // 等于的部分
i++;
}
}
swap(nums, tl - 1, l);
tl--;
tg++;
// [l,tl)<V, [tg,r)>V, [tl,tg) = V
if (k >= tl && k < tg) {
return nums[k];
} else if (k < tl) {
r = tl;
} else {
l = tg;
}
}
while (true);
}
private void swap(int[] arr, int i, int j) {
int t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}
}