题目描述
有一个整数数组，请你根据快速排序的思路，找出数组中第 k 大的数。
给定一个整数数组 a ,同时给定它的大小n和要找的 k ，请返回第 k 大的数(包括重复的元素，不用去重)，保证答案存在。
要求：时间复杂度 O(nlogn)，空间复杂度 O(1)
示例
- 示例1
输入：[1,3,5,2,2],5,3
输出：2 - 示例2
输入：[10,10,9,9,8,7,5,6,4,3,4,2],12,3
输出：9
说明：去重后的第3大是8，但本题要求包含重复的元素，不用去重，所以输出9 。
方法思路
典型的快速排序
1、进行一次快排，大元素在左，小元素在右，得到的中轴p点；
2、如果 p - low + 1 = k ，那么p点就是第K大。
3、如果 p - low + 1 > k，则第k大的元素在左半段，更新high = p - 1，执行step 1。
4、如果 p - low + 1 < k，则第k大的元素在右半段，更新low = p + 1, 且 k = k - (p - low + 1)，排除掉前面部分更大的元素，再执行step 1。
import java.util.*;
public class Solution {
//常规的快排划分，但是这次是大数在左
public int partion(int[] a,int low,int high){
int temp = a[low];
while(low<high){
//小于标杆的在右
while(low<high && a[high]<=temp){
high--;
}
if(low==high){
break;
}else{
a[low] = a[high];
}
//大于标杆的在左
while(low<high && a[low]>=temp){
low++;
}
if(low==high){
break;
}else{
a[high] = a[low];
}
}
a[low] = temp;
return low;
}
public int quickSort(int[] a,int low,int high,int K){
//先进行一轮划分，p下标左边的都比它大，下标右边都比它小
int p = partion(a,low,high);
//若p刚好是第K个点，则找到
if(K == p-low+1){
return a[p];
}else if(p-low+1>K){
//从头到p超过k个数组，则目标在左边
return quickSort(a,low,p-1,K);
}else{
//否则，在右边，递归右边，但是需要减去左边最大的数字的数量
return quickSort(a,p+1,high,K-(p-low+1));
}
}
public int findKth(int[] a, int n, int K) {
// write code here
return quickSort(a,0,n-1,K);
}
}
