思路很多：
1.将整个数组排序之后的第k个
2.大小为k的小顶堆
3.quick-select，即快排的partition函数，每次都能将一个放在应该的位置，如果
该位置是k-1，那么就是要找的元素
1.时间:O(nlgn),空间O(1)
2.时间(nlgk),空间(k)
3.时间O(kn)???O(n)??
本题要做出来不难，但是要想起到比较好的复习作用，需要做的工作很多：
1我们一般会选择快排，那么和3会共用一个partition函数
而对于快排，要保证o(nlgn) 的时间复杂度，需要确保数组无序，所以需要实现shuffle
而对于2，我们当然可以直接使用java的priorityqueue，但是也可以自己实现堆（以上的内容都是算法4cover到的）
import java.util.Random; class Solution { private void shuffle(int[] nums) { Random random = new Random(); for (int i = nums.length - 1; i > 0; i--) { int j = random.nextInt(i + 1); swap(nums, i, j); } } private void swap(int[] a, int i, int j) { int t = a[i]; a[i] = a[j]; a[j] = t; } // 在[lo,hi]中选一个元素（一般是第一个），然后将所有比他小的移动到他的左边，大的移动到右边 // 结束时应该左边都是比他小的，右边都是比他大的 private int partition(int[] nums, int lo, int hi) { int pivot = nums[lo]; int i = lo, j = hi; // 扫描范围在[lo,hi],[i,j]组成的范围不断缩小 while (i <= j) { // 从左到右，找到一个比pivot大的，如果找到，停止，如果没有(i指向了hi，扫描了所有的数），也停止 while (nums[i] <= pivot) { i++; if (i == hi) { break; } } // 这里同上 while (nums[j] >= pivot) { j--; if (j == lo) { break; } } // 如果区间里已经没有数或者是一个数，那么i，j不用再交换，退出循环 if (i >= j) { break; } swap(nums, i, j); } // 注意lo是我们的pivot // 而j如果不等于lo，那么j是比pivot小的（注意内层循环终止条件），而pivot是最左端的，所以pivot应该和j互换 // 交换之后，pivot所在的index为j，所以返回j swap(nums, lo, j); return j; } // quick select： public int findKthLargest(int[] nums, int k) { shuffle(nums); int lo=0,hi=nums.length-1; // 当返回的位置是len-k时结束 int target=nums.length-k; while(lo<hi){ int j=partition(nums,lo,hi); if(target==j){ return nums[j]; }else if(target<j){ hi=j-1; }else if(target>j){ lo=j+1; } } return nums[target]; } } import java.util.Random; class Solution { private void shuffle(int[] nums) { Random random = new Random(); for (int i = nums.length - 1; i > 0; i--) { int j = random.nextInt(i + 1); swap(nums, i, j); } } private void swap(int[] a, int i, int j) { int t = a[i]; a[i] = a[j]; a[j] = t; } // 在[lo,hi]中选一个元素（一般是第一个），然后将所有比他小的移动到他的左边，大的移动到右边 // 结束时应该左边都是比他小的，右边都是比他大的 private int partition(int[] nums, int lo, int hi) { int pivot = nums[lo]; int i = lo, j = hi; // 扫描范围在[lo,hi],[i,j]组成的范围不断缩小 while (i <= j) { // 从左到右，找到一个比pivot大的，如果找到，停止，如果没有(i指向了hi，扫描了所有的数），也停止 while (nums[i] <= pivot) { i++; if (i == hi) { break; } } // 这里同上 while (nums[j] >= pivot) { j--; if (j == lo) { break; } } // 如果区间里已经没有数或者是一个数，那么i，j不用再交换，退出循环 if (i >= j) { break; } swap(nums, i, j); } // 注意lo是我们的pivot // 而j如果不等于lo，那么j是比pivot小的（注意内层循环终止条件），而pivot是最左端的，所以pivot应该和j互换 // 交换之后，pivot所在的index为j，所以返回j swap(nums, lo, j); return j; } private void quickSort(int[] nums, int lo, int hi) { if (lo >= hi) { return; } int p = partition(nums, lo, hi); quickSort(nums, lo, p - 1); quickSort(nums, p + 1, hi); } private void quickSort(int[] nums) { shuffle(nums); quickSort(nums, 0, nums.length - 1); } public int findKthLargest(int[] nums, int k) { quickSort(nums); // 升序，返回倒数第k个 return nums[nums.length-k]; } public static void main(String[] args) { int[] a = {1, 2, 3, 4, 5}; new Solution().quickSort(a); System.out.println(); } }
