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

Question

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

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

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

Answer 1

相信在你使用quickselest找到第k-th个静态之后，你会自动发现k结果数组的第一个元素是k最小的元素，只是可能没有排序。

此外，quickselect 实际上对第 -th 个统计信息进行了分区k：第 -th 个统计信息之前的所有元素k都小于（或等于）它，而其后的所有元素都大于或等于。这很容易证明。

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

其他元素没有任何特定的顺序，除了第 n 个之前的元素没有一个大于它，并且它后面的元素没有一个小于它。

如果你不仅需要k最小的元素，还需要排序的 k最小元素，你当然可以在 quickselect 之后对它们进行排序。

Answer 2

实际上不需要修改quickselect。如果我有一个数组（在本例中称为 arrayToSearch）并且我想要 k 个最小的项目，我会这样做：

int i;
int k = 10;  // if you wanted the 10 smallest elements 
int smallestItems = new Array(k);
for (i = 0; i < k; i++)
{
    smallestItems[i] = quickselect(i, arrayToSearch);
}

编辑：我假设 k 是一个相对较小的数字，这将使得有效的 Big-O O(n) 。如果不假设 k 很小，则速度为 O(k*n)，而不是线性时间。我的答案更容易理解，并且适用于大多数实际目的。recursion.ninja 的答案可能在技术上更正确，因此更适合学术目的。