小编Rat*_*565的帖子

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

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

我的方法:

我找到了中位数:

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

之后:

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

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

我想证明具有n个节点的Fibonacci堆可以具有高度n.

我用例子尝试了这个,但我不知道如何在一般情况下显示这个.