假设您有一个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)运行.任何帮助将不胜感激 :)
algorithm selection
algorithm ×1
selection ×1