arrays - 为数组中最小的 k 个元素调整快速选择

Question

我知道我可以通过使用 quickselect 获得第 K 个顺序统计信息(即数组中的第 k 个最小数)几乎是线性时间，但如果我需要数组的 k 个最小元素怎么办？

维基百科链接有一个用于单元素查找的伪代码，但没有用于第 k 个最小元素s 查找的伪代码。

应该如何修改 quickselect 以在线性时间内实现它(如果可能)？

Answer 1

我相信在使用 quickselest 找到第 k 个静态变量后，您会自动发现结果数组的前 k 元素是 k 最小的元素，可能只是未排序。

此外，quickselect 实际上对第 k 个统计数据进行分区:第 k 个统计数据之前的所有元素都较小(或等于)，并且后面的所有元素都大于或等于。这很容易证明。

请注意，例如对于 C++ nth_element

The other elements are left without any specific order, except that none of the elements preceding nth are greater than it, and none of the elements following it are less.

如果您不仅需要 k 个最小元素，还需要排序 k 个最小元素，您当然可以在快速选择之后对它们进行排序。