数组中的第K个最大元素
给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。
示例 1:
输入: [3,2,1,5,6,4], k = 2
输出: 5
示例 2:
输入: [3,2,3,1,2,4,5,5,6], k = 4
输出: 4
思路
方案一：快速选择
题目要求找到给定数组 nums 中的第 k 大元素。为了实现这个目标，可以采用 快速选择 算法，这是一种基于快速排序的思想，可以在平均时间复杂度为 O(n) 的情况下解决这个问题。
快速选择（Quick Select）算法的核心思想
- 选择基准：选择数组中的一个基准元素，通常选择第一个元素或随机选择。
- 分区操作：通过划分操作，将数组分成两部分，基准元素左边的部分所有元素小于等于基准元素，右边的部分所有元素大于等于基准元素。
- 递归查找
- 如果基准元素的索引正好是
k-1，则返回该元素。 - 如果基准元素的索引大于
k-1，则继续在左半部分查找。 - 如果基准元素的索引小于
k-1，则继续在右半部分查找。
- 如果基准元素的索引正好是
class Solution {
public int findKthLargest(int[] nums, int k) {
int n = nums.length;
int low = 0, high = n - 1;
while(true){
int povit = partition(nums, low, high);
if (povit == k-1){
return nums[povit];
}else if(povit > k-1){
high = povit - 1;
}else{
low = povit + 1;
}
}
}
private int partition(int[] nums, int low, int high){
int povit = nums[low];
while(low < high){
while(low < high && nums[high] <= povit) --high;
nums[low] = nums[high];
while(low < high && nums[low] >= povit) ++low;
nums[high] = nums[low];
}
nums[low] = povit;
return low;
}
}
代码分析
findKthLargest 方法
- 初始化：
n：数组nums的长度。low：指向数组的起始位置，初始为0。high：指向数组的末尾，初始为n - 1。
- 循环：使用
while(true)来持续进行 快速选择 直到找到第k大的元素。- 调用
partition(nums, low, high)方法来划分数组。 - 基准值的索引
povit是划分后的元素的索引，它是数组的一个"分界点"。 - 判断 povit 是否等于 k - 1：
- 如果
povit == k - 1，表示找到第k大的元素，直接返回nums[povit]。 - 如果
povit > k - 1，说明第k大的元素在左半部分，因此将high更新为povit - 1。 - 如果
povit < k - 1，说明第k大的元素在右半部分，因此将low更新为povit + 1。
- 如果
- 调用
partition 方法
- 初始化：
povit是选定的基准元素，这里选定了nums[low]作为基准。
- 划分过程：
- 使用两个指针
low和high，通过遍历来将数组中的元素分成两部分：小于等于基准的元素放在基准的左边，大于等于基准的元素放在右边。 - 步骤：
- 内层循环：从右边开始，寻找小于等于基准的元素，然后交换到左边。
- 内层循环：从左边开始，寻找大于等于基准的元素，然后交换到右边。
- 最终，基准元素
povit会被交换到low索引的位置，数组被分成了两部分。
- 使用两个指针
- 返回值：
- 返回
low，即基准元素的最终位置。
- 返回
方案二：堆
堆是一种常用的用于查找第 K 大/小元素的数据结构。可以使用最小堆（Min-Heap）或者最大堆（Max-Heap），具体选择哪一种取决于你是要查找第 K 大还是第 K 小元素。
小根堆（Min-Heap）求第 K 大元素
-
小根堆的堆顶是最小的元素，所以它总是保持堆中最小的元素在堆顶。
-
为了找到第 K 大元素，我们可以构建一个大小为 K 的小根堆，然后遍历数组中的其他元素：
- 如果堆中有 K 个元素，且当前元素大于堆顶元素，就将堆顶元素移除，插入当前元素。
- 最后，堆顶元素就是第 K 大的元素。
大根堆（Max-Heap）求第 K 小元素
-
大根堆的堆顶是最大的元素，所以它总是保持堆中最大元素在堆顶。
-
为了找到第 K 小元素，我们可以构建一个大小为 K 的大根堆，然后遍历数组中的其他元素：
- 如果堆中有 K 个元素，且当前元素小于堆顶元素，就将堆顶元素移除，插入当前元素。
- 最后，堆顶元素就是第 K 小的元素。
具体解释
- 小根堆求第 K 大元素：我们使用小根堆维护一个包含 K 个最大元素的堆。由于小根堆的特性，堆顶是当前堆中最小的元素。因此，当堆中元素超过 K 个时，我们移除堆顶，保留较大的元素。最终堆顶就会是第 K 大的元素。
- 大根堆求第 K 小元素：我们使用大根堆维护一个包含 K 个最小元素的堆。由于大根堆的特性，堆顶是当前堆中最大的元素。当堆中元素超过 K 个时，我们移除堆顶，保留较小的元素。最终堆顶就是第 K 小的元素。
class Solution {
public int findKthLargest(int[] nums, int k) {
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
for(int num : nums){
minHeap.add(num);
//假如有m个元素，留下来的k个就等于是最大的那k个，
//然后取这里面最小的一个就行了
if(minHeap.size() > k){
minHeap.poll();
}
}
return minHeap.peek();
}
}