LeetCode Hot100 215.数组中的第k个最大元素
题目：
给定整数数组nums和整数k，请返回数组中第k个最大的元素。
请注意，你需要找的是数组排序后的第k个最大的元素，而不是第k个不同的元素。
你必须设计并实现时间复杂度为O(n)的算法解决此问题。
方法一：内部 api 排序
class Solution { public int findKthLargest(int[] nums, int k) { Arrays.sort(nums); int n = nums.length; return nums[n - k]; } }方法二：堆排序
class Solution { public int findKthLargest(int[] nums, int k) { PriorityQueue<Integer> heap = new PriorityQueue<>(); // 小顶堆 for (int num : nums) { heap.offer(num); if (heap.size() > k) // 让堆始终保持k个元素,多于k时让堆顶即最小的出 heap.poll(); // 出堆顶,即最小的元素 } return heap.peek(); // 返回堆顶元素 } }小顶堆：每个节点的值都小于或等于其左右孩子的值
大顶堆：每个节点的值都大于或等于其左右孩子的值
方法三、灵神（二分+快排）
class Solution { private static final Random rand = new Random(); public int findKthLargest(int[] nums, int k) { int n = nums.length; int targetIndex = n - k; // 第 k 大元素在升序数组中的下标是 n - k int left = 0; int right = n - 1; // 闭区间 while (true) { int i = partition(nums, left, right); if (i == targetIndex) { // 找到第 k 大元素 return nums[i]; } if (i > targetIndex) { // 第 k 大元素在 [left, i - 1] 中 right = i - 1; } else { // 第 k 大元素在 [i + 1, right] 中 left = i + 1; } } } // 在子数组 [left, right] 中随机选择一个基准元素 pivot // 根据 pivot 重新排列子数组 [left, right] // 重新排列后，<= pivot 的元素都在 pivot 的左侧，>= pivot 的元素都在 pivot 的右侧 // 返回 pivot 在重新排列后的 nums 中的下标 // 特别地，如果子数组的所有元素都等于 pivot，我们会返回子数组的中心下标，避免退化 private int partition(int[] nums, int left, int right) { // 1. 在子数组 [left, right] 中随机选择一个基准元素 pivot int i = left + rand.nextInt(right - left + 1); int pivot = nums[i]; // 把 pivot 与子数组第一个元素交换，避免 pivot 干扰后续划分，从而简化实现逻辑 swap(nums, i, left); // 2. 相向双指针遍历子数组 [left + 1, right] // 循环不变量：在循环过程中，子数组的数据分布始终如下图 // [ pivot | <=pivot | 尚未遍历 | >=pivot ] // ^ ^ ^ ^ // left i j right i = left + 1; int j = right; while (true) { while (i <= j && nums[i] < pivot) { i++; } // 此时 nums[i] >= pivot while (i <= j && nums[j] > pivot) { j--; } // 此时 nums[j] <= pivot if (i >= j) { break; } // 维持循环不变量 swap(nums, i, j); i++; j--; } // 循环结束后 // [ pivot | <=pivot | >=pivot ] // ^ ^ ^ ^ // left j i right // 3. 把 pivot 与 nums[j] 交换，完成划分（partition） // 为什么与 j 交换？ // 如果与 i 交换，可能会出现 i = right + 1 的情况，已经下标越界了，无法交换 // 另一个原因是如果 nums[i] > pivot，交换会导致一个大于 pivot 的数出现在子数组最左边，不是有效划分 // 与 j 交换，即使 j = left，交换也不会出错 swap(nums, left, j); // 交换后 // [ <=pivot | pivot | >=pivot ] // ^ // j // 返回 pivot 的下标 return j; } // 交换 nums[i] 与 nums[j] private void swap(int[] nums, int i, int j) { int tmp = nums[i]; nums[i] = nums[j]; nums[j] = tmp; } }j是“小于等于区”的最后一个索引，i是“大于等于区”的第一个索引