使快速选择适应数组中最小的k个元素 [英] Adapting quickselect for smallest k elements in an array

问题描述

我知道我可以通过使用

I know that I can get the Kth order statistic (i.e. the kth smallest number in an array) by using quickselect in almost linear time, but what if I needed the k smallest elements of an array?

Wikipedia链接具有用于单元素查找的伪代码，但没有用于k个最小元素 s 查找的伪代码.

The wikipedia link has a pseudocode for the single-element lookup, but not for the k smallest elements lookup.

应该如何修改quickselect以在线性时间内获得它(如果可能)?

How should quickselect be modified to attain it in linear time (if possible) ?

推荐答案

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

Actually modifying quickselect is not needed. If I had an array (called arrayToSearch in this example) and I wanted the k smallest items I'd do this:

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的答案在技术上可能更正确，因此更适合学术目的.

I was under the assumption that k would be a relatively small number which would make the effective Big-O O(n). If not assuming k is small this would have a speed of O(k*n), not linear time. My answer is easier to comprehend, and applicable for most practical purposes. recursion.ninja's answer may be more technically correct, and therefore better for academic purposes.

这篇关于使快速选择适应数组中最小的k个元素的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！