在O(n)时间复杂度内找到数组中第k小的元素

Question

3

在时间复杂度为O(n)的情况下，能否返回未排序数组中最小的k个整数？假设我们返回答案的顺序不重要。一些方法使用有序数据结构（如堆）以O(n log k)的时间完成此任务，但我认为我们可以使用修改后的Quickselect算法在O(n)的时间内完成。这样对吗？

- Daniel

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- templatetypedef · Accepted Answer

是的，这是可能的。你要找的术语是选择算法，其中有几种算法的时间复杂度为O(n)，包括快速选择算法（严格来说，它的期望时间复杂度是O(n)）。

其中一些算法通过重新排列原始数组的元素，将第k个最小元素放置在位置k，所有比位置k小的元素放在位置k的左边，所有比位置k大的元素放在位置k的右边。使用其中一种算法，要找到前k个最小元素，只需使用选择算法将第k个最小元素放置在位置k，然后读取位置小于k的元素即可。

其他算法会返回第k个最小元素是什么，但不会重新排列元素。在这种情况下，你可以简单地遍历数组，并输出所有小于第k个最小元素的元素。