今天分享的题目来源于 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];
}
}
复杂度分析
到这里，我们已经分析出了：
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;
int target = len - k;
while (true) {
int index = partition(nums, left, right);
if (index == target) {
return nums[index];
} else if (index left = index + 1;
} else {
assert index > target;
right = index - 1;
}
}
}
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]
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;
}
}
复杂度分析
方法三：优先队列
优先队列的写法就很多了，这里例举一下我能想到的。
假设数组有
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 参考代码
import java.util.PriorityQueue;
public class Solution {
public int findKthLargest(int[] nums, int k) {
int len = nums.length;
PriorityQueue minHeap = new PriorityQueue<>(len, (a, b) -> a - b);
for (int i = 0; i minHeap.add(nums[i]);
}
for (int i = 0; i minHeap.poll();
}
return minHeap.peek();
}
}
思路 2 参考代码
import java.util.PriorityQueue;
public class Solution {
public int findKthLargest(int[] nums, int k) {
int len = nums.length;
PriorityQueue maxHeap = new PriorityQueue<>(len, (a, b) -> b - a);
for (int i = 0; i maxHeap.add(nums[i]);
}
for (int i = 0; i 1; i++) {
maxHeap.poll();
}
return maxHeap.peek();
}
}
思路 3 参考代码
import java.util.PriorityQueue;
public class Solution {
public int findKthLargest(int[] nums, int k) {
int len = nums.length;
PriorityQueue minHeap = new PriorityQueue<>(k, (a, b) -> a - b);
for (int i = 0; i minHeap.add(nums[i]);
}
for (int i = k; i
Integer topEle = minHeap.peek();
if (nums[i] > topEle) {
minHeap.poll();
minHeap.add(nums[i]);
}
}
return minHeap.peek();
}
}
思路 4 参考代码
import
