数组中的第K个最大元素
数组中的第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
二、解题思路
对于寻找数组中第K大元素的问题，有几种常见的解法：
1. 排序法
最直观的方法是将数组排序后，直接返回第k大的元素：
Arrays.sort(nums);
return nums[nums.length - k];
复杂度分析：
- 时间复杂度：O(n log n)，不满足题目要求的O(n)
- 空间复杂度：O(1) 或 O(log n)，取决于排序算法的实现
2. 堆排序法
维护一个大小为k的最小堆，遍历数组，将元素加入堆中：
PriorityQueue<Integer> minHeap = new PriorityQueue<>(k);
for (int num : nums) {
minHeap.offer(num);
if (minHeap.size() > k) {
minHeap.poll();
}
}
return minHeap.peek();
复杂度分析：
- 时间复杂度：O(n log k)，不满足题目要求的O(n)
- 空间复杂度：O(k)
3. 快速选择算法
快速选择算法是基于快速排序的分治算法，但只处理包含目标元素的那一部分，可以达到平均O(n)的时间复杂度。这是解决本题的最优方法。
三、快速选择算法详解
1. 算法原理
快速选择算法的核心思想是：
- 选择一个基准元素（pivot）
- 将数组分为两部分：小于基准的元素和大于基准的元素
- 根据基准元素的位置与目标位置的关系，决定在哪一部分继续查找
对于第k大元素，我们可以将其转换为查找第(n-k)小的元素，其中n是数组长度。
2. 分区操作
分区操作是快速选择算法的核心，其目的是将数组分为两部分：
- 左边的元素都小于等于基准元素
- 右边的元素都大于基准元素
分区操作的步骤：
- 选择一个基准元素（通常选择最右边的元素）
- 使用两个指针i和j：
- i指向小于等于基准元素区域的边界
- j用于遍历数组
- 当nums[j] <= pivot时，交换nums[i]和nums[j]，并将i向右移动一步
- 最后，将基准元素放到正确的位置（i与right交换）
- 返回基准元素的位置i
3. 算法流程
快速选择算法的整体流程：
- 调用分区操作，获取基准元素的位置pivotIndex
- 比较pivotIndex与目标位置k：
- 如果pivotIndex == k，找到了目标元素，返回nums[pivotIndex]
- 如果pivotIndex < k，在右子数组中继续查找
- 如果pivotIndex > k，在左子数组中继续查找
- 递归调用，直到找到目标元素
4. 代码实现
public int findKthLargest(int[] nums, int k) {
// 转换为查找第(n-k)小的元素的索引
int targetIndex = nums.length - k;
return quickSelect(nums, 0, nums.length - 1, targetIndex);
}
private int quickSelect(int[] nums, int left, int right, int k) {
// 分区操作，返回基准元素的位置
int pivotIndex = partition(nums, left, right);
if (pivotIndex == k) {
// 找到了第k小的元素
return nums[pivotIndex];
} else if (pivotIndex < k) {
// 第k小的元素在右子数组
return quickSelect(nums, pivotIndex + 1, right, k);
} else {
// 第k小的元素在左子数组
return quickSelect(nums, left, pivotIndex - 1, k);
}
}
private int partition(int[] nums, int left, int right) {
//可以先 随机选择一个元素作为基准，避免最坏情况
//int randomIndex = left + (int) (Math.random() * (right - left + 1));
//swap(nums, randomIndex, right);
// 选择最右边的元素作为基准
int pivot = nums[right];
int i = left;
// 将小于基准的元素放到左边
for (int j = left; j < right; j++) {
if (nums[j] <= pivot) {
swap(nums, i, j);
i++;
}
}
// 将基准放到正确位置
swap(nums, i, right);
return i; // 返回基准位置
}
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
四、图解快速选择过程
1. 示例数组
以数组 [3,2,1,5,6,4] 为例，查找第2大的元素（即第5小的元素，targetIndex = 6 - 2 = 4）：
初始状态：
数组: [3, 2, 1, 5, 6, 4]
↑ ↑
left right
i=0 pivot=4
2. 第一次分区
选择基准元素 pivot = 4：
-
遍历数组，j从left开始：
- j=0: nums[0]=3 <= pivot, 交换nums[0]和nums[0]（实际不变），i++
数组: [3, 2, 1, 5, 6, 4] ↑ i=1,j=0- j=1: nums[1]=2 <= pivot, 交换nums[1]和nums[1]（实际不变），i++
数组: [3, 2, 1, 5, 6, 4] ↑ i=2,j=1- j=2: nums[2]=1 <= pivot, 交换nums[2]和nums[2]（实际不变），i++
数组: [3, 2, 1, 5, 6, 4] ↑ i=3,j=2- j=3: nums[3]=5 > pivot, 不交换，i不变
数组: [3, 2, 1, 5, 6, 4] ↑ ↑ i=3 j=3- j=4: nums[4]=6 > pivot, 不交换，i不变
数组: [3, 2, 1, 5, 6, 4] ↑ ↑ i=3 j=4 -
交换nums[i]和nums[right]，将基准元素放到正确位置：
数组: [3, 2, 1, 4, 6, 5] ↑ i=3 (pivotIndex) -
比较pivotIndex(3)与targetIndex(4)：
- pivotIndex < targetIndex，在右子数组中继续查找
3. 第二次分区
在右子数组 [6,5] 中继续查找：
数组: [3, 2, 1, 4, 6, 5]
↑ ↑
left right
i=4 pivot=5
-
遍历数组，j从left开始：
- j=4: nums[4]=6 > pivot, 不交换，i不变
数组: [3, 2, 1, 4, 6, 5] ↑ ↑ i=4 j=4 -
交换nums[i]和nums[right]，将基准元素放到正确位置：
数组: [3, 2, 1, 4, 5, 6] ↑ i=4 (pivotIndex) -
比较pivotIndex(4)与targetIndex(4)：
- pivotIndex == targetIndex，找到了目标元素，返回nums[4] = 5
4. 结果分析
通过两次分区操作，我们成功找到了数组中的第2大元素：5。
整个过程中，我们只处理了包含目标元素的那部分数组，而不需要对整个数组进行排序，这就是快速选择算法高效的原因。
五、算法优化
1. 随机选择基准元素
为了避免在已排序或近似排序的数组上性能下降，可以随机选择基准元素：
private int partition(int[] nums, int left, int right) {
// 随机选择一个元素作为基准
int randomIndex = left + (int) (Math.random() * (right - left + 1));
swap(nums, randomIndex, right);
// 其余代码不变
int pivot = nums[right];
// ...
}
2. 三数取中法
另一种选择基准元素的方法是三数取中法，即选择left、right和mid三个位置的元素的中间值作为基准：
private int partition(int[] nums, int left, int right) {
int mid = left + (right - left) / 2;
// 排序left, mid, right三个位置的元素
if (nums[left] > nums[mid]) swap(nums, left, mid);
if (nums[left] > nums[right]) swap(nums, left, right);
if (nums[mid] > nums[right]) swap(nums, mid, right);
// 将中间值（现在在mid位置）交换到right-1位置
swap(nums, mid, right - 1);
// 使用nums[right-1]作为基准
int pivot = nums[right - 1];
// ...
}
3. 非递归实现
为了避免递归调用导致的栈溢出，可以使用迭代方式实现快速选择：
public int findKthLargest(int[] nums, int k) {
int left = 0;
int right = nums.length - 1;
int targetIndex = nums.length - k;
while (left <= right) {
int pivotIndex = partition(nums, left, right);
if (pivotIndex == targetIndex) {
return nums[pivotIndex];
} else if (pivotIndex < targetIndex) {
left = pivotIndex + 1;
} else {
right = pivotIndex - 1;
}
}
return -1; // 不会执行到这里
}
六、复杂度分析
1. 时间复杂度
-
平均情况：==O(n)==
- 每次分区操作会将问题规模减少一半（平均情况）
- 总时间复杂度为：T(n) = T(n/2) + O(n) = O(n)
-
最坏情况：O(n²)
- 如果每次都选到最大或最小元素作为基准
- 但通过随机选择基准元素，最坏情况的概率很低
2. 空间复杂度
-
递归实现：
- 平均情况：O(log n)，递归调用栈的深度
- 最坏情况：O(n)，递归调用栈的深度
-
迭代实现：O(1)，只使用常数级别的额外空间
七、总结
问：如何在O(n)时间内找到数组中的第K大元素？
关键知识点
快速选择算法是解决第K大元素问题的最优方法，它基于快速排序的分区思想，但只处理包含目标元素的那一部分数组。通过将第K大元素转换为第(n-k+1)小元素，然后使用分区操作递归查找，可以在平均O(n)时间内找到目标元素。
深入解析
-
快速选择算法的核心思想：
- 利用分区操作将数组分为两部分
- 根据基准元素位置与目标位置的关系，决定在哪一部分继续查找
- 避免对整个数组排序，只关注包含目标元素的部分
-
分区操作的工作原理：
- 选择基准元素（pivot）
- 将小于等于基准的元素放在左边
- 将大于基准的元素放在右边
- 返回基准元素的最终位置
-
常见的进阶问题：
- 如何处理有大量重复元素的数组？
答：可以使用三路快速选择，将数组分为小于、等于和大于基准的三部分 - 如何优化最坏情况下的性能？
答：使用随机选择基准元素或三数取中法 - 如果内存受限，如何处理大规模数据？
答：可以使用迭代而非递归实现，或考虑外部排序技术
- 如何处理有大量重复元素的数组？
本文是原创文章，采用 CC BY-NC-ND 4.0 协议，完整转载请注明来自 程序员小刘
评论
匿名评论
隐私政策
你无需删除空行，直接评论以获取最佳展示效果
欢迎联系
