在时间复杂度为O(n)的情况下,能否返回未排序数组中最小的k个整数?假设我们返回答案的顺序不重要。一些方法使用有序数据结构(如堆)以O(n log k)的时间完成此任务,但我认为我们可以使用修改后的Quickselect算法在O(n)的时间内完成。这样对吗?
是的,这是可能的。你要找的术语是选择算法,其中有几种算法的时间复杂度为O(n),包括快速选择算法(严格来说,它的期望时间复杂度是O(n))。其中一些算法通过重新排列原始数组的元素,将第k个最小元素放置在位置k,所有比位置k小的元素放在位置k的左边,所有比位置k大的元素放在位置k的右边。使用其中一种算法,要找到前k个最小元素,只需使用选择算法将第k个最小元素放置在位置k,然后读取位置小于k的元素即可。其他算法会返回第k个最小元素是什么,但不会重新排列元素。在这种情况下,你可以简单地遍历数组,并输出所有小于第k个最小元素的元素。