0215. Kth Largest Element in an Array
======================================
题目信息
--------
:题号: 0215. 数组中的第 K 个最大元素
:难度: Medium
:主题: 数组、选择问题、排序、堆、快速选择
:原题: `LeetCode 0215 `_
:重点: 第 K 大转为升序下标、重复值排名、划分不变量、只保留目标分区
题目重述
--------
给定未排序整数数组 ``nums`` 和整数 ``k``,返回按非递增顺序排列后第 ``k`` 个位置的元素值。重复值按出现位置计数,
所以这是“排名位置”而不是“第 k 个不同数值”。算法可以原地重排数组,函数只需要返回一个整数。
数组非空,``1 <= k <= nums.size()``;元素可能为负数,输入不保证互异。
自建示例
--------
``nums = [7,2,9,4,9]``、``k=2`` 的降序排列为 ``[9,9,7,4,2]``,答案是 ``9``;两个相同的 9 占据两个排名位置。
``nums = [-3,-1,-2]``、``k=3`` 返回 ``-3``。数组长度为 ``n`` 时,第 ``k`` 大元素在升序排列中的下标是 ``target=n-k``,
不是 ``k-1``。
``nums = [5,5,5]``、``k=2`` 返回 ``5``;所有元素相等时目标仍由位置定义,不需要去重。
C++ 实现
--------
.. code-block:: cpp
#include
#include
#include
#include
class Solution {
private:
static int selectBySorting(std::vector nums, int target) {
std::sort(nums.begin(), nums.end());
return nums[target];
}
static int selectByHeap(const std::vector& nums, int k) {
std::priority_queue, std::greater> heap;
for (int value : nums) {
if (static_cast(heap.size()) < k) {
heap.push(value);
} else if (value > heap.top()) {
heap.pop();
heap.push(value);
}
}
return heap.top();
}
static int selectByPartition(std::vector& nums, int target) {
int left = 0;
int right = static_cast(nums.size()) - 1;
while (left <= right) {
const int pivot = nums[left + (right - left) / 2];
int less = left;
int current = left;
int greater = right;
while (current <= greater) {
if (nums[current] < pivot) {
std::swap(nums[less++], nums[current++]);
} else if (nums[current] > pivot) {
std::swap(nums[current], nums[greater--]);
} else {
++current;
}
}
if (target < less) {
right = less - 1;
} else if (target > greater) {
left = greater + 1;
} else {
return nums[target];
}
}
return nums[target];
}
public:
int findKthLargest(std::vector& nums, int k) {
const int target = static_cast(nums.size()) - k;
return selectByPartition(nums, target);
}
};
题解
----
排名转换与被删除的全序
~~~~~~~~~~~~~~~~~~~~~~~~
排序后取 ``nums[n-k]`` 是最直接的方案。它正确地把第 ``k`` 大转换为升序下标 ``target=n-k``,并且重复值按排名位置保留;
但它还建立了目标两侧完全不需要的相对顺序,时间为 ``O(n log n)``。固定大小的最小堆只保存最大的 ``k`` 个值,时间降为
``O(n log k)``、空间为 ``O(k)``,但仍为每个元素维护堆序。
快速选择只确定一个排名
~~~~~~~~~~~~~~~~~~~~~~~~
在当前闭区间选枢轴,把元素分成小于、等于、大于三段。目标下标只可能落在其中一段:落在等于段时答案已经确定;落在一侧时,
另一侧及等于段都不再需要排序。三向划分因此把“全数组排序”压缩成“只继续处理目标所在区间”,同时一次封闭全部重复值。
三向划分不变量
~~~~~~~~~~~~~~~~
先转成升序目标下标 ``target``。每轮开始时,``[left,right]`` 是尚未排除的区间,目标一定在其中。扫描区间内维护:
* ``[left,less)`` 全部小于枢轴;
* ``[less,current)`` 全部等于枢轴;
* ``(greater,right]`` 全部大于枢轴;
* ``[current,greater]`` 尚未分类。
当前值小于枢轴时,把它换到 ``less`` 并同时推进 ``less``、``current``;等于枢轴时只推进 ``current``;大于枢轴时与 ``greater``
交换,但不能推进 ``current``,因为换回来的元素尚未分类。划分完成后,目标在左段就收缩 ``right``,在右段就收缩 ``left``,
落在等于段则直接返回。
状态走读
~~~~~~~~
仍以 ``[7,2,9,4,9]`` 为例,设枢轴为 9:
.. list-table::
:header-rows: 1
* - 区域
- 含义
- 划分结果
* - ``[left,less)``
- 小于 9
- ``[7,2,4]``
* - ``[less,greater]``
- 等于 9
- ``[9,9]``
* - ``(greater,right]``
- 大于 9
- 空
* - ``target=3``
- 目标位于等于段
- 返回 9
目标落在左段时的收缩
~~~~~~~~~~~~~~~~~~~~~~
对 ``[7,2,9,4,9]``、``k=2``,``target=3``,取枢轴 9:小于段为 ``[7,2,4]``,等于段为 ``[9,9]``,目标落在等于段,
所以无需知道 7、4、2 的彼此顺序即可返回 9。若目标改为 1,右边界就直接移到等于段左侧;这一步正是删除旧搜索空间的地方。
重复值为何单独成段
~~~~~~~~~~~~~~~~~~~~
若只划分为 ``< pivot`` 和 ``>= pivot``,与枢轴相等的元素会反复进入下一轮,目标位于重复值中间时会重新扫描已经确定的值。
三向划分一次封闭整个等值段,重复值越多,删除的无关工作越多。
代码演进与方案选择
~~~~~~~~~~~~~~~~~~~~
``selectBySorting`` 适合还需要完整有序数组的场景,时间 ``O(n log n)``;``selectByHeap`` 只维护前 ``k`` 名,
当 ``k`` 很小时空间和调整成本更低,但仍需 ``O(n log k)``;``selectByPartition`` 只保留目标区间,平均线性且原地,
代价是枢轴选择不佳时最坏会退化为 ``O(n^2)``,并且会重排输入。公共入口选择三向快速选择,因为本题只需要一个排名,
重复值又是必须明确处理的边界;两个私有替代方法保留的是不同的搜索压缩认识,而不是重复代码。
代码中 ``nums[current] > pivot`` 的分支不推进 ``current``,这是状态不变量的直接映射;交换回来的元素仍未分类,提前推进会使它漏检。
``target=n-k``、三段指针和原地交换分别对应排名转换、等值封闭和目标区间收缩。
复杂度与边界
~~~~~~~~~~~~
排序法时间 ``O(n log n)``,复制参数时工作空间为 ``O(n)``;堆法时间 ``O(n log k)``、空间 ``O(k)``;三向快速选择平均时间 ``O(n)``、
额外空间 ``O(1)``,最坏时间 ``O(n^2)``。``k=1``、``k=n``、所有元素相等和单元素数组都由同一划分状态处理;主解允许原地修改输入,
若调用者需要保留原顺序,应在外层复制后再调用。