超详细！详解一道高频算法题：数组中的第 K 个最大元素
source link: https://www.cxyxiaowu.com/3024.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
点击蓝色“五分钟学算法”关注我哟
加个“星标”，天天中午 12:15，一起学算法
作者 | 李威
来源 | https://www.liwei.party/
整理 | 五分钟学算法
今天分享的题目来源于 LeetCode 第 215 号问题，是面试中的高频考题。
在 未排序 的数组中找到第 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 ≤ 数组的长度。
方法一：返回升序排序以后索引为 len – k 的元素
题目已经告诉你了：
你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
因此，升序排序以后，返回索引为 len – k 这个元素即可。
这是最简单的思路，如果只答这个方法，可能面试官并不会满意，但是在我们平时的开发工作中，还是不能忽视这种思路简单的方法，我认为理由如下：
1、最简单同时也一定是最容易编码的，编码成功的几率最高，可以用这个最简单思路编码的结果和其它思路编码的结果进行比对，验证高级算法的正确性；
2、在数据规模小、对时间复杂度、空间复杂度要求不高的时候，真没必要上 “高大上” 的算法；
3、思路简单的算法考虑清楚了，有些时候能为实现高级算法铺路。这道题正是如此，“数组排序后的第 k 个最大的元素” ，语义是从右边往左边数第 k 个元素（从 1 开始），那么从左向右数是第几个呢，我们列出几个找找规律就好了。
一共 6 个元素，找第 2 大，索引是 4；
一共 6 个元素，找第 4 大，索引是 2。
因此，目标元素的索引是 len – k，即找最终排定以后位于 len – k 的那个元素；
4、低级算法往往容错性最好，即在输入不满足题目条件的时候，往往还能得到正确的答案，而高级算法对输入数据的要求就非常苛刻。
import java.util.Arrays;
public class Solution {
public int findKthLargest(int[] nums, int k) {
int len = nums.length;
Arrays.sort(nums);
return nums[len - k];
}
}
复杂度分析
- 时间复杂度：O(NlogN)。这里 N 是数组的长度，算法的性能消耗主要在排序，JDK 默认使用快速排序，因此时间复杂度为O(NlogN)。
- 空间复杂度：O(1)。这里是原地排序，没有借助额外的辅助空间。
到这里，我们已经分析出了：
1、我们应该返回最终排定以后位于 len – k 的那个元素；
2、性能消耗主要在排序，JDK 默认使用快速排序。
学习过 “快速排序” 的朋友，一定知道一个操作叫 partition，它是 “分而治之” 思想当中 “分” 的那一步。
经过 partition 操作以后，每一次都能排定一个元素，并且这个元素左边的数都不大于它，这个元素右边的数都不小于它，并且我们还能知道排定以后的元素的索引。
于是可以应用 “减而治之”（分治思想的特例）的思想，把问题规模转化到一个更小的范围里。
于是得到方法二。
方法二：借助 partition 操作定位
方法二则是借助 partition 操作定位到最终排定以后索引为 len – k 的那个元素。
以下的描述基于 “快速排序” 算法知识的学习，如果忘记的朋友们可以翻一翻自己的《数据结构与算法》教材，复习一下，partition 过程、分治思想和 “快速排序” 算法的优化。
我们在学习 “快速排序” 的时候，接触的第 1 个操作就是 partition（切分），简单介绍如下：
partition（切分）操作，使得：
- 对于某个索引 j，nums[j] 已经排定，即 nums[j] 经过 partition（切分）操作以后会放置在它 “最终应该放置的地方”；
- nums[left] 到 nums[j – 1] 中的所有元素都不大于 nums[j]；
- nums[j + 1] 到 nums[right] 中的所有元素都不小于 nums[j]。
partition（切分）操作总能排定一个元素，还能够知道这个元素它最终所在的位置，这样每经过一次 partition操作就能缩小搜索的范围，这样的额思想叫做 “减而治之”（是 “分而治之” 思想的特例）。
切分过程可以不借助额外的数组空间，仅通过交换数组元素实现。下面是参考代码：
public class Solution {
public int findKthLargest(int[] nums, int k) {
int len = nums.length;
int left = 0;
int right = len - 1;
// 转换一下，第 k 大元素的索引是 len - k
int target = len - k;
while (true) {
int index = partition(nums, left, right);
if (index == target) {
return nums[index];
} else if (index < target) {
left = index + 1;
} else {
assert index > target;
right = index - 1;
}
}
}
/**
* 在 nums 数组的 [left, right] 部分执行 partition 操作，返回 nums[i] 排序以后应该在的位置
* 在遍历过程中保持循环不变量的语义
* 1、(left, k] < nums[left]
* 2、(k, i] >= nums[left]
*
* @param nums
* @param left
* @param right
* @return
*/
public int partition(int[] nums, int left, int right) {
int pivot = nums[left];
int j = left;
for (int i = left + 1; i <= right; i++) {
if (nums[i] < pivot) {
// 小于 pivot 的元素都被交换到前面
j++;
swap(nums, j, i);
}
}
// 最后这一步不要忘记了
swap(nums, j, left);
return j;
}
private void swap(int[] nums, int index1, int index2) {
if (index1 == index2) {
return;
}
int temp = nums[index1];
nums[index1] = nums[index2];
nums[index2] = temp;
}
}
复杂度分析
- 时间复杂度：O(N)。这里 N 是数组的长度。
- 空间复杂度：O(1)。这里是原地排序，没有借助额外的辅助空间。
方法三：优先队列
优先队列的写法就很多了，这里例举一下我能想到的。
假设数组有 len 个元素。
思路 1 ：把 len 个元素都放入一个最小堆中，然后再 pop() 出 len – k 个元素，此时最小堆只剩下 k 个元素，堆顶元素就是数组中的第 k 个最大元素。
思路 2 ：把 len 个元素都放入一个最大堆中，然后再 pop() 出 k – 1 个元素，因为前 k – 1 大的元素都被弹出了，此时最大堆的堆顶元素就是数组中的第 k 个最大元素。
思路 3 ：只用 k 个容量的优先队列，而不用全部 len 个容量。
思路 4：用 k + 1 个容量的优先队列，使得上面的过程更“连贯”一些，到了 k 个以后的元素，就进来一个，出去一个，让优先队列自己去维护大小关系。
思路 5：综合考虑以上两种情况，总之都是为了节约空间复杂度。即 k 较小的时候使用最小堆，k 较大的时候使用最大堆。
根据以上思路，分别写出下面的代码：
思路 1 参考代码
//思路 1 ：把 len 个元素都放入一个最小堆中，然后再 pop() 出 len - k 个元素，此时最小堆只剩下 k 个元素，堆顶元素就是数组中的第 k 个最大元素。
import java.util.PriorityQueue;
public class Solution {
public int findKthLargest(int[] nums, int k) {
int len = nums.length;
// 使用一个含有 len 个元素的最小堆，默认是最小堆，可以不写 lambda 表达式：(a, b) -> a - b
PriorityQueue<Integer> minHeap = new PriorityQueue<>(len, (a, b) -> a - b);
for (int i = 0; i < len; i++) {
minHeap.add(nums[i]);
}
for (int i = 0; i < len - k; i++) {
minHeap.poll();
}
return minHeap.peek();
}
}
思路 2 参考代码
//思路 2 ：把 len 个元素都放入一个最大堆中，然后再 pop() 出 k - 1 个元素，因为前 k - 1 大的元素都被弹出了，此时最大堆的堆顶元素就是数组中的第 k 个最大元素。
import java.util.PriorityQueue;
public class Solution {
public int findKthLargest(int[] nums, int k) {
int len = nums.length;
// 使用一个含有 len 个元素的最大堆，lambda 表达式应写成：(a, b) -> b - a
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(len, (a, b) -> b - a);
for (int i = 0; i < len; i++) {
maxHeap.add(nums[i]);
}
for (int i = 0; i < k - 1; i++) {
maxHeap.poll();
}
return maxHeap.peek();
}
}
思路 3 参考代码
//思路 3 ：只用 k 个容量的优先队列，而不用全部 len 个容量。
import java.util.PriorityQueue;
public class Solution {
public int findKthLargest(int[] nums, int k) {
int len = nums.length;
// 使用一个含有 k 个元素的最小堆
PriorityQueue<Integer> minHeap = new PriorityQueue<>(k, (a, b) -> a - b);
for (int i = 0; i < k; i++) {
minHeap.add(nums[i]);
}
for (int i = k; i < len; i++) {
// 看一眼，不拿出，因为有可能没有必要替换
Integer topEle = minHeap.peek();
// 只要当前遍历的元素比堆顶元素大，堆顶弹出，遍历的元素进去
if (nums[i] > topEle) {
minHeap.poll();
minHeap.add(nums[i]);
}
}
return minHeap.peek();
}
}
思路 4 参考代码
//思路 4：用 k + 1 个容量的优先队列，使得上面的过程更“连贯”一些，到了 k 个以后的元素，就进来一个，出去一个，让优先队列自己去维护大小关系。
import java.util.PriorityQueue;
public class Solution {
public int findKthLargest(int[] nums, int k) {
int len = nums.length;
// 最小堆
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(k + 1, (a, b) -> (a - b));
for (int i = 0; i < k; i++) {
priorityQueue.add(nums[i]);
}
for (int i = k; i < len; i++) {
priorityQueue.add(nums[i]);
priorityQueue.poll();
}
return priorityQueue.peek();
}
}
思路 5 参考代码
//思路 5：综合考虑以上两种情况，总之都是为了节约空间复杂度。即 k 较小的时候使用最小堆，k 较大的时候使用最大堆。
import java.util.PriorityQueue;
public class Solution {
// 根据 k 的不同，选最大堆和最小堆，目的是让堆中的元素更小
// 思路 1：k 要是更靠近 0 的话，此时 k 是一个较大的数，用最大堆
// 例如在一个有 6 个元素的数组里找第 5 大的元素
// 思路 2：k 要是更靠近 len 的话，用最小堆
// 所以分界点就是 k = len - k
public int findKthLargest(int[] nums, int k) {
int len = nums.length;
if (k <= len - k) {
// System.out.println("使用最小堆");
// 特例：k = 1，用容量为 k 的最小堆
// 使用一个含有 k 个元素的最小堆
PriorityQueue<Integer> minHeap = new PriorityQueue<>(k, (a, b) -> a - b);
for (int i = 0; i < k; i++) {
minHeap.add(nums[i]);
}
for (int i = k; i < len; i++) {
// 看一眼，不拿出，因为有可能没有必要替换
Integer topEle = minHeap.peek();
// 只要当前遍历的元素比堆顶元素大，堆顶弹出，遍历的元素进去
if (nums[i] > topEle) {
minHeap.poll();
minHeap.add(nums[i]);
}
}
return minHeap.peek();
} else {
// System.out.println("使用最大堆");
assert k > len - k;
// 特例：k = 100，用容量为 len - k + 1 的最大堆
int capacity = len - k + 1;
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(capacity, (a, b) -> b - a);
for (int i = 0; i < capacity; i++) {
maxHeap.add(nums[i]);
}
for (int i = capacity; i < len; i++) {
// 看一眼，不拿出，因为有可能没有必要替换
Integer topEle = maxHeap.peek();
// 只要当前遍历的元素比堆顶元素大，堆顶弹出，遍历的元素进去
if (nums[i] < topEle) {
maxHeap.poll();
maxHeap.add(nums[i]);
}
}
return maxHeap.peek();
}
}
}
———————–
公众号：五分钟学算法（ID：CXYxiaowu）
博客：www.cxyxiaowu.com
知乎：程序员吴师兄
一个正在学习算法的人，致力于将算法讲清楚！
长按下图二维码关注，和你一起领悟算法的魅力。
原文始发于微信公众号（五分钟学算法）：超详细！详解一道高频算法题：数组中的第 K 个最大元素
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK