Leetcode面试经典150题-215.数组中的第K个最大元素

解法都在代码里，不懂就留言或者私信

我提供两种解法，第一种堆的解法实测也是能过的，所以实在想不起来第二种就用第一种也行

class Solution {/**题目要求时间复杂度是O(n)，所以所有的排序都不能考虑了，这里我们使用堆来解决把所有的数放入堆里，堆里的元素按照从顶向下依次增大的排序方式，所有的数都加完之后顶上就是我们要的其实这里的时间复杂度是O(nlongk)*/public int findKthLargestHeap(int[] nums, int k) {/**就一个数，又肯定存在，那就第一个数把 */if(nums.length == 1) {return nums[0];}PriorityQueue<Integer> heap = new PriorityQueue<>();/**把所有的数尝试入堆*/for(int num : nums) {/**堆不满直接入 */if(heap.size() < k) {heap.offer(num);} else {/**只有大于堆顶的情况下（比原来的最大的k个数大） */if(num > heap.peek()) {heap.poll();heap.offer(num);}/**不大于堆顶自己放弃 */}}return heap.peek();}/**真正的O(n)的解，只partition，不排序，每次只走一边 */public int findKthLargest(int[] nums, int k) {/**这个题目和我们之前做过的某个题目有点像，题号我想不起来了，大概就是假设数组排序，第k大的数是多少，注意这里只是假设排序，不能真的排，如果真的排，时间复杂度就是O(n*logn)了，我们这里利用一下快排的思想1.先随机选出一个数，然后看看这个数的等于区间的范围，如果k刚好在等于区间，那我们要的就是这个数 2.如果k应该在小于区间，就从小于区间随机选出一个数重复1的操作3.如果k应该在大于区间，就从大于区间随机选出一个数重复1的操作这样一直递归下去，直到命中1的条件为止，注意这里是按照快排的思想从大到小排序，不然设计下标转换容易懵*/return findKthLargest(nums, 0, nums.length - 1,k);}/**返回如果按照从大到小排序，排序之后的第k大的数（下标为k-1）*/public int findKthLargest(int[] nums, int start, int end, int k) {if(start >= end) {return nums[start];}/**随机选取一个数作为基准值 */int randomIndex = start + (int)(Math.random() * (end - start));int[] equalsRange = partition(nums, start, end, nums[randomIndex]);if(equalsRange[0] <= k - 1 && equalsRange[1] >= k-1) {/**这里千万要写equalsRange[0]或者k-1或者euqalsRange[1]也行，就是别写randomIndex，因为它变了。。。 */return nums[equalsRange[0]];} else if(equalsRange[0] > k - 1) {return findKthLargest(nums, start, equalsRange[0] - 1, k);} else {return findKthLargest(nums, equalsRange[1] + 1, end, k);}}public int[] partition(int[] nums, int start, int end, int pivot) {if(start == end) {return new int[] {start, start};}/**如果大于等于两个数，从start为止开始遍历，遍历的过程中1.如果当前数等于pivot，不交换，curIndex++2.如果当前数大于pivot跟大于区域的下一个数交换，大于区域右扩3.如果当前数小于pivot跟小于区域的前一个数交换，小于区域左扩*/int curIndex = start;/**大于区域的右边界，现在还没有大于区域，所以这里取start-1 */int greaterRightBound = start - 1;/**小于区域的左边界，现在还没有小于区域，这里取end+1 */int lessLeftBound = end + 1;while(curIndex < lessLeftBound) {if(nums[curIndex] == pivot) {curIndex ++;} else if(nums[curIndex] > pivot) {swap(nums, curIndex++, ++greaterRightBound);} else {swap(nums, curIndex, --lessLeftBound);}}return new int[] {greaterRightBound + 1, lessLeftBound - 1};}public void swap(int[] nums, int i, int j) {int temp = nums[i];nums[i] = nums[j];nums[j] = temp;}
}