随机选择算法

要求时间复杂度为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 nnums.length; int ans0; for(int l0,rn-1;lr;){ partition(nums,l,r,nums[l(int) (Math.random()*(r-l1))]); if(n-kfirst){ rfirst-1; } else if(n-klast){ llast1; } else{ ansnums[n-k]; break; } } return ans; } public static int first,last; public static void partition(int[] nums,int l,int r,int x){ firstl; lastr; int il; while(ilast){ 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 tempnums[i]; nums[i]nums[j]; nums[j]temp; } }额外空间复杂度o(1)