215. Kth Largest Element in an Array

题目描述和难度

题目描述：

在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

示例 1:

输入: [3,2,1,5,6,4] 和 k = 2 输出: 5

示例 2:

输入: [3,2,3,1,2,4,5,5,6] 和 k = 4 输出: 4

说明:

你可以假设 k 总是有效的，且 1 ≤ k ≤ 数组的长度。

题目难度：中等。英文网址：215. Kth Largest Element in an Array 。中文网址：215. 数组中的第K个最大元素 。

思路分析

求解关键：这是一个常规问题，使用借用快速排序的 partition 的思想完成。关键在于理解 partition 的返回值，返回值是拉通了整个数组的索引值，这一点是非常重要的，不要把问题想得复杂了。

partition 这个函数返回的是整个数组的第 k 个最小元素（从 0 开始计算）。如果找第 k 个最小元素，即第 n - k 个最大元素。

例如：给定数组为：[2,5,6,1,4,7] ，一共 6 个元素 找 k = 2，如果返回 4 ，就可以返回了。 给定数组为：[2,5,6,1,4,7] ，一共 6 个元素 找 k = 2，如果返回 2 ，左边的区间就可以不用看了。

参考解答

参考解答1：使用快速排序的 partition 的思想完成。

public class Solution2 { private static Random random = new Random(System.currentTimeMillis()); public int findKthLargest(int[] nums, int k) { int len = nums.length; if (len == 0 || k > len) { throw new IllegalArgumentException("参数错误"); } // 转换一下，这样比较好操作 // 第 k 大元素的索引是 len - k int target = len - k; int l = 0; int r = len - 1; while (true) { int i = partition(nums, l, r); if (i < target) { l = i + 1; } else if (i > target) { r = i - 1; } else { return nums[i]; } } } // 在区间 [left, right] 这个区间执行 partition 操作 private int partition(int[] nums, int left, int right) { // 在区间随机选择一个元素作为标定点（以下这两行代码非必需） // 这一步优化非必需 if (right > left) { int randomIndex = left + 1 + random.nextInt(right - left); swap(nums, left, randomIndex); } int pivot = nums[left]; int l = left; for (int i = left + 1; i <= right; i++) { if (nums[i] < pivot) { l++; swap(nums, l, i); } } swap(nums, left, l); return l; } private void swap(int[] nums, int index1, int index2) { if (index1 == index2) { return; } int temp = nums[index1]; nums[index1] = nums[index2]; nums[index2] = temp; } }

参考解答2：使用最小堆，这个写法是我最开始的写法，有点死板。

public class Solution3 { public int findKthLargest(int[] nums, int k) { int len = nums.length; if (len == 0 || k > len) { throw new IllegalArgumentException("参数错误"); } // 使用一个含有 k 个元素的最小堆 PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(k, (a, b) -> a - b); for (int i = 0; i < k; i++) { priorityQueue.add(nums[i]); } for (int i = k; i < len; i++) { // 看一眼 Integer topEle = priorityQueue.peek(); // 只要当前遍历的元素比堆顶元素大，堆顶出栈，遍历的元素进去 if (nums[i] > topEle) { priorityQueue.poll(); priorityQueue.add(nums[i]); } } return priorityQueue.peek(); } }

参考解答3：最小堆更简单的写法。

public class Solution3 { public int findKthLargest(int[] nums, int k) { PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(k + 1, (a, b) -> (a - b)); for (int num : nums) { priorityQueue.add(num); if(priorityQueue.size()==k+1){ priorityQueue.poll(); } } return priorityQueue.peek(); } }

本篇文章的地址为 https://liweiwei1419.github.io/leetcode-solution/leetcode-0215-kth-largest-element-in-an-array ，如果我的题解有错误，或者您有更好的解法，欢迎您告诉我 liweiwei1419@gmail.com 。