我知道我可以在几乎线性时间内使用quickselect得到第k阶统计量(即数组中的第k个最小数),但是如果我需要数组中的k个最小元素呢?
wikipedia链接有一个用于单元素查找的伪代码,但不用于k个最小元素查找。
应如何修改QuickSelect以在线性时间内实现它(如果可能)?

最佳答案

实际上不需要修改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是一个相对较小的数,这将使有效的大o(n)。如果不假设k很小,则速度为o(k*n),而不是线性时间。我的答案更容易理解,而且适用于大多数实际用途。递归。忍者的答案可能在技术上更正确,因此在学术上更好。

10-06 05:19
查看更多