随机选择算法

要求时间复杂度为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)