题目描述
给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
需要注意的是：
这里找的是“第
k个最大的元素”，不是“第k个不同的元素”。
也就是说，如果数组中有重复数字，重复数字也要参与排名。
示例分析
示例 1
输入: nums = [3,2,1,5,6,4], k = 2
输出: 5
把数组从大到小排列后是：
[6,5,4,3,2,1]
第 2 个最大的元素就是 5。
示例 2
输入: nums = [3,2,3,1,2,4,5,5,6], k = 4
输出: 4
从大到小排列后是：
[6,5,5,4,3,3,2,2,1]
第 4 个最大的元素是 4。
解题思路
最直接的想法当然是：
-
先排序
-
再取第
k个元素
比如升序排序后取 nums[nums.length - k]，或者降序排序后取 nums[k - 1]。
这种方法可以做出来，但时间复杂度是：
O(n log n)
而这道题其实有更高效的做法：快速选择（Quick Select）。
你给出的代码就是快速选择的写法。
什么是快速选择
快速选择可以理解成“只做一部分排序”。
它和快速排序的思想很像，都是先选一个基准值 pivot，再把数组分成几部分。
但区别在于：
-
快速排序会递归处理左右两边，直到整个数组有序
-
快速选择只会递归进入目标元素所在的那一边
所以它不需要把整个数组都排好序，只需要不断缩小范围，直到找到答案。
这就是它比完整排序更快的原因。
这份代码的核心思想
你给出的代码不是原地分区版本，而是一个更容易理解的版本：
-
随机选一个
pivot -
把数组分成三部分：
-
big：比pivot大的数 -
equal：等于pivot的数 -
small：比pivot小的数
-
-
判断第
k大元素落在哪一部分 -
只递归进入那一部分继续找
代码如下：
public class Solution {
private int quickSelect(List<Integer> nums, int k) {
Random rand = new Random();
int pivot = nums.get(rand.nextInt(nums.size()));
List<Integer> big = new ArrayList<>();
List<Integer> equal = new ArrayList<>();
List<Integer> small = new ArrayList<>();
for (int num : nums) {
if (num > pivot)
big.add(num);
else if (num < pivot)
small.add(num);
else
equal.add(num);
}
if (k <= big.size())
return quickSelect(big, k);
if (nums.size() - small.size() < k)
return quickSelect(small, k - nums.size() + small.size());
return pivot;
}
public int findKthLargest(int[] nums, int k) {
List<Integer> numList = new ArrayList<>();
for (int num : nums) {
numList.add(num);
}
return quickSelect(numList, k);
}
}
为什么要分成三部分
很多同学第一次做这题时，会以为只要分成两部分：
-
大于
pivot -
小于等于
pivot
但你这里分成三部分其实更清晰：
-
big -
equal -
small
这样做的好处是：
如果第
k大正好落在equal这部分，那么答案就直接是pivot，不需要继续递归。
尤其当数组中有很多重复元素时，这种写法会更自然。
核心判断逻辑
假设当前数组被分成：
-
big.size()个比pivot大的数 -
equal.size()个等于pivot的数 -
small.size()个比pivot小的数
那么第 k 大元素有三种可能：
1. 落在 big 中
如果：
k <= big.size()
说明第 k 大元素一定还在 big 这一部分里。
因为 big 中的所有元素都比 pivot 大，所以排名靠前的元素一定先从 big 里找。
于是递归：
return quickSelect(big, k);
2. 落在 equal 中
如果第 k 大不在 big 里，但它又没有落到 small 里，那么它一定就在 equal 里。
这时答案就是：
return pivot;
3. 落在 small 中
如果第 k 大元素既不在 big，也不在 equal，那么它一定在 small 中。
不过这时排名要重新计算。
因为：
-
big中的元素排在前面 -
equal中的元素也排在前面
所以进入 small 后，第 k 大就要减掉前面已经跳过的元素数量。
你的代码里写的是：
if (nums.size() - small.size() < k)
return quickSelect(small, k - nums.size() + small.size());
这里：
nums.size() - small.size()
其实就是：
big.size() + equal.size()
也就是前面已经排掉的元素个数。
所以新的排名变成：
k - (big.size() + equal.size())
也就是：
k - nums.size() + small.size()
代码解析
1. 随机选取基准值
Random rand = new Random();
int pivot = nums.get(rand.nextInt(nums.size()));
这里随机从当前数组中取一个数作为 pivot。
为什么要随机？
因为如果每次都固定选某个位置，可能在某些特殊数据下退化得比较严重。 随机选择可以让平均性能更稳定。
2. 分成三组
List<Integer> big = new ArrayList<>();
List<Integer> equal = new ArrayList<>();
List<Integer> small = new ArrayList<>();
for (int num : nums) {
if (num > pivot)
big.add(num);
else if (num < pivot)
small.add(num);
else
equal.add(num);
}
这里按照与 pivot 的大小关系，把当前数组拆成三部分。
因为题目要求找“第 k 大”，所以这里优先把“大于 pivot” 的数放进 big。
3. 第 k 大在 big 中
if (k <= big.size())
return quickSelect(big, k);
说明目标还在更大的那一边，继续递归查找。
4. 第 k 大在 small 中
if (nums.size() - small.size() < k)
return quickSelect(small, k - nums.size() + small.size());
说明第 k 大已经越过了：
-
所有比
pivot大的元素 -
所有等于
pivot的元素
所以要去 small 中找新的第若干大元素。
5. 否则答案就是 pivot
return pivot;
说明第 k 大恰好落在 equal 这一段中。
6. 主函数把数组转成 List
public int findKthLargest(int[] nums, int k) {
List<Integer> numList = new ArrayList<>();
for (int num : nums) {
numList.add(num);
}
return quickSelect(numList, k);
}
因为辅助函数是基于 List<Integer> 写的，所以先把数组转换成列表。
示例推演
我们以这个例子来模拟：
nums = [3,2,1,5,6,4], k = 2
目标是找第 2 大元素。
假设随机选出的 pivot = 4。
那么分组后：
big = [5,6]
equal = [4]
small = [3,2,1]
因为：
k = 2
big.size() = 2
满足：
k <= big.size()
所以第 2 大元素一定在 big 中。
继续递归：
quickSelect([5,6], 2)
假设这次随机选 pivot = 5。
分组后：
big = [6]
equal = [5]
small = []
这时：
-
k = 2 -
big.size() = 1 -
big.size() + equal.size() = 2
说明第 2 大元素正好落在 equal 中。
于是直接返回：
5
这就是答案。
为什么快速选择比排序更高效
排序的目标是：
把所有元素的相对顺序都确定下来
但这道题只需要：
找到一个位置上的元素
所以没有必要把整个数组都排好序。
快速选择每次都只进入一边递归，平均情况下会把问题规模迅速缩小，因此平均时间复杂度可以做到：
O(n)
而完整排序需要：
O(n log n)
所以当题目只问“第 k 大 / 第 k 小”时，快速选择往往更合适。
复杂度分析
设数组长度为 n。
时间复杂度
平均时间复杂度为：
O(n)
因为每次划分后，只递归进入一侧。
最坏情况下会退化到：
O(n^2)
比如每次选到的 pivot 都很差。
但由于这里使用了随机选择基准值，平均表现通常很好。
空间复杂度
这份代码不是原地分区写法，而是额外创建了：
-
big -
equal -
small
所以空间复杂度为：
O(n)
如果写成原地 partition 版本，空间复杂度可以优化到 O(1)（不算递归栈）。
和排序解法对比
排序解法
优点：
-
非常直接
-
容易想到
-
代码简洁
缺点：
-
时间复杂度是
O(n log n) -
做了很多不必要的排序工作
快速选择解法
优点：
-
平均时间复杂度更优，为
O(n) -
只关心目标位置，不需要完整排序
缺点：
-
思维难度比排序稍高
-
最坏情况下可能退化
-
这份三数组写法需要额外空间
总结
这道题的核心不是排序，而是：
如何不把整个数组排好序，也能快速确定第
k大元素。
快速选择的关键思想就是：
-
随机选一个基准值
pivot -
按照与
pivot的大小关系，把数组分成三部分 -
判断第
k大落在哪一部分 -
只递归进入那一部分继续查找
你可以把这题总结成一句话：
快速选择就是“只找目标，不排全局”的快速排序思想。
这类题非常经典，后面像：
-
第 K 小元素
-
数组中的中位数
-
TopK 问题
