更新时间：2025-04-04
- 算法题解目录汇总：算法刷题记录——题解目录汇总
- 技术博客总目录：计算机技术系列博客——目录页
优先整理热门100及面试150，不定期持续更新，欢迎关注！
215. 数组中的第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
提示：
1 <= k <= nums.length <= 10^5-10^4 <= nums[i] <= 10^4
方法：三向切分快速选择法
利用快速选择算法结合三向切分，高效定位第K大元素。
三向切分：
- 将数组分为三个区域：大于基准值、等于基准值、小于基准值；
- 采用类似荷兰国旗问题的分区方式，一次遍历完成分类；
递归选择：
- 根据当前分区后的元素数量分布，决定递归处理方向；
- 大于区域元素足够时递归处理前部；
- 数量不足但包含等于区域时直接返回基准值；
- 否则递归处理后部并调整k值；
随机选择基准值避免最坏情况，每次递归至少排除一个区域元素。
代码实现(Java)：
class Solution {
public int findKthLargest(int[] nums, int k) {
return quickSelect(nums, 0, nums.length - 1, k);
}
private int quickSelect(int[] nums, int left, int right, int k) {
if (left == right) {
return nums[left];
}
Random rand = new Random();
int pivotIndex = left + rand.nextInt(right - left + 1);
int pivot = nums[pivotIndex];
// 三向切分（荷兰国旗问题）
int low = left;
int high = right;
int mid = left;
while (mid <= high) {
if (nums[mid] > pivot) { // 大于pivot的交换到前部
swap(nums, low, mid);
low++;
mid++;
} else if (nums[mid] < pivot) { // 小于pivot的交换到后部
swap(nums, mid, high);
high--;
} else { // 等于时继续后移
mid++;
}
}
// 计算各区域元素数量
int gtCount = low - left; // 大于pivot的数目
int eqCount = high - low + 1; // 等于pivot的数目
if (k <= gtCount) { // 目标在大于区域
return quickSelect(nums, left, low - 1, k);
} else if (k <= gtCount + eqCount) { // 目标在等于区域
return pivot;
} else { // 目标在小于区域
return quickSelect(nums, high + 1, right, k - gtCount - eqCount);
}
}
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
复杂度分析
平均时间复杂度 O(n)，最坏情况 O(n^2)。
声明
- 本文版权归
CSDN用户Allen Wurlitzer所有，遵循CC-BY-SA协议发布，转载请注明出处。- 本文题目来源
力扣-LeetCode，著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。