如何计算最接近中位数的k？

Question

我有一个n个成对不同元素的数组和一个数字k,其中1 <= k <= n.

现在我正在寻找一种算法,计算k数字与数字数组的中位数的最小绝对差值.我需要线性复杂度(O(n)).

我的方法:

我找到了中位数:

• 我把数字排序
• 我得到了中间元素,或者如果元素的数量为id,那么中间和圆形中的两个元素的平均值.

之后:

• 我拿每个数字,找到距离中位数的绝对距离.这些结果我保存在不同的数组中
• 我对新获得的数组进行排序.
• 我取结果数组的前k个元素,我就完成了.

我不知道我的解决方案是否存在O(n),我是否对这个想法是对的.有人可以验证吗？有人能告诉我如何在O(n)中解决它吗？

Answer 1

你可以像这样解决你的问题:

您可以O(n)使用O(n) nth_element算法找到wg 的中位数.

你循环遍历所有用一对代替的元素:<the absolute difference to the median>, <element's value>.再次使用n= 执行nth_element k.应用此算法后,您可以保证k在新数组中首先具有绝对差异的最小元素.你拿他们的指数和完成!

另一方面,您的算法使用排序,这就成了它O(nlogn).

编辑:请求的示例:

让阵列成为[14, 6, 7, 8, 10, 13, 21, 16, 23].

• 在找到中位数的步骤之后,它将被重新排序,比如说:[8, 7, 9, 10, 13, 16, 23, 14, 21]注意数组没有排序,但中位数(13)仍在中间.
• 现在让我们做一对让你困惑的对替换:我们创建一个新的对数组:[<abs(14-13), 14>, <abs(6-13), 6>, <abs(7-13), 7>, <abs(8-13), 8>, <abs(10-13), 10>, <abs(13-13), 13>, <abs(21-13), 21>, <abs(16-13), 16>, <abs(23-13), 23>.因此我们获得了数组:[<1, 14>, <7, 6>, <6, 7>, <5, 8>, <3, 10>, <0, 13>, <8, 21>, <3, 16>, <10, 23>
• 如果例如k是4我们使再次nth_element(使用每对用于比较的第一个元素),将获得:[<1, 14>, <3, 16>, <0, 13>, <3, 10>, <8, 21>, <7, 6>, <10, 23>, <6, 7>, <5, 8>]因此您搜索号码的前4对的第二元素:14,16,13和10