要求时间复杂度为o(n)，所有不能排序处理
可以利用快速排序的方法，数组长度为n,第K大为 求n-k位置的数
随机一个数X，用X进行划分，<X,=X,>X区域，如果n-k在=X区域中，返回X即可
如果n-k在小于X的区域，再在该区域重新进行划分，大于X的区域同理，递归下去
class Solution {
public int findKthLargest(int[] nums, int k) {
int n=nums.length;
int ans=0;
for(int l=0,r=n-1;l<=r;){
partition(nums,l,r,nums[l+(int)
(Math.random()*(r-l+1))]);
if(n-k<first){
r=first-1;
}
else if(n-k>last){
l=last+1;
}
else{
ans=nums[n-k];
break;
}
}
return ans;
}
public static int first,last;
public static void partition(int[] nums,int l,int r,int x){
first=l;
last=r;
int i=l;
while(i<=last){
if(nums[i]==x){
i++;
}
else if(nums[i]<x){
swap(nums,first++,i++);
}
else{
swap(nums,last–,i);
}
}
}
public static void swap(int[] nums,int i,int j){
int temp=nums[i];
nums[i]=nums[j];
nums[j]=temp;
}
}
额外空间复杂度o(1)
