LeetCode 题解之 215. Kth Largest Element in an Array

xiaoxiao2021-02-28  8

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 。

转载请注明原文地址: https://www.6miu.com/read-2250285.html

最新回复(0)