选择算法问题

Question

假设您有一个n个项目的数组A,并且您希望在A中找到最接近A的中位数的k项.例如,如果A包含9个值{7,14,10,12,2,1,2,29 ,3,4}和k = 5,然后答案将是值{7,14,10,12,11},因为中位数是10,这些是A中最接近值10的五个值.给出一个在O(n)时间内解决这个问题的算法.

我知道选择算法(深度选择)是这个问题的合适算法,但我认为这将在O(n*logn)时间而不是O(n)运行.任何帮助将不胜感激 :)

Answer 1

您首先需要找到中位数,这可以在O(n)(例如使用Hoare的Quickselect算法)中完成.

然后,您将需要实现一种排序算法,该算法根据它们与中位数的绝对距离(首先是最小距离)对数组中的元素进行排序.

如果您以这种方式对整个数组进行排序,这通常需要从某个位置O(n * log n)开始O(n^2),具体取决于所使用的算法.但是,由于您只需要第一个k值,因此复杂性可以降低O(k * log n)到O(k * n).

由于k是常数并且不依赖于数组的大小,因此在最坏情况下的总体复杂性将是:( O(n)用于找到中值)+ O(k * n)(排序),这是O(n)总体的.