二刷hot100-215.数组中第k个最大元素

有点复杂随机找一个基准索引令该元素的右边均小于他左边均大于他在这个操作的过程中也有很多细节是先把基准元素放到了此次操作范围的最后边然后int p nums[r]; int i r; while(l r){ while(l r nums[l] p){ l 1; } while(l r nums[r] p){ r - 1; } if(l r){ switch0(nums,l,r); } }之后交换基准元素和l对应元素class Solution { public int findKthLargest(int[] nums, int k) { return quicksort(nums,0,nums.length - 1,k); } public int quicksort(int[] nums,int l,int r,int k){ int index randomselect(nums,l,r); if(index k - 1){ return nums[index]; }else if(index k - 1){ return quicksort(nums,l,index - 1,k); }else{ return quicksort(nums,index 1,r,k); } } public int randomselect(int[] nums,int l,int r){ int index (int)(Math.random() * (r - l 1)) l; swap(nums,r,index); return f(nums,l,r); } public void swap(int[] nums,int r,int index){ int temp nums[r]; nums[r] nums[index]; nums[index] temp; } public int f(int[] nums,int l,int r){ int i r; while(l r){ while(l r nums[l] nums[i]){ l; } while(l r nums[r] nums[i]){ r--; } if(l r){ swap(nums,l,r); } } swap(nums,l,i); return l; } }