问题标签 [median-of-medians]

就个人而言，我认为中位数的中位数不是真正的中位数。正确的？
那么如果上面的说法是正确的，为什么使用中位数的中位数作为支点来划分数组以找到第 Kth min elem 的时间复杂度最坏情况是 O(n) 呢？“n”是元素的数量。

终于找到bug了，请看第二个EDIT
但是还有那个问题，你看，“getMedian()”方法的最后第四行，我对medians[]数组进行排序，求出中位数的中位数。我个人认为这打破了最坏情况的时间复杂度 = O(n)，对吗？

---

我尝试使用中位数的中位数作为枢轴来划分数组以找到第 K 个最大元素。

但是这个 bug 很奇怪：例如 {8, 5, 2, 0, 9, 1}，输出是：

• k = 1，输出 >> 9。
• k = 2，输出 >> 9。
• k = 3，输出 >> 5。
• k = 4，输出 >> 2。
• k = 5，输出 >> 1。
• k = 6，输出 >> 0。
• 第二个最大元素的输出是错误的，其他的很好。

另一个问题：

在getMedian (int[] givenArray, int start, int end)方法的最后第二行，我对中位数数组进行排序，我认为这个操作打破了 O(n) 的时间复杂度，对吗？

---

编辑
我个人认为，该错误可能存在于两个地方：

• 在“ partition (int[] givenArray, int start, int end, int pivot)”
• >

[代码]

• 在“ findKthMax_MOM_Helper (int[] givenArray, int start, int end, int k)”
• >

[代码]

---

第二次编辑
最后我发现了这个错误，我的代码的错误部分是在“getMedian()”方法处，看看那个方法的最后三句话。
[代码]

我意识到这个问题已经被问过一百万次了，但我希望这有点不同，更有趣一点。我遇到了 Dor 和 Zwick 的论文，该论文说可以在 <= 3n 比较中找到 n 个整数数组中的中位数。论文在这里： http ://eccc.hpi-web.de/report/1995/031/download

有没有人真正实现过这个？它看起来非常复杂，我很乐意看到它运行以将其与更标准的算法版本进行比较。

中位数快速排序的最坏情况时间复杂度是多少（枢轴由需要 O(n) 时间才能找到的中位数的中位数确定）？

我使用 Medians of Medians 实现了一个 nth_number 选择算法。在wikipedia上，它指出它的空间复杂度是 O(1)

我必须将中位数存储在一个临时数组中，以便在这些中位数中找到中位数。在不使用任何额外内存的情况下如何做到这一点？如果它不算增加它的空间复杂度，请解释一下。

我知道线性选择（中位数算法的中位数）递归方程如下：

但是这些术语是从哪里来的呢？我一直在努力理解，但我非常困惑。任何人都可以阐明一下吗？

我是一名 compsci 学生，我在分析与设计 II 课上收到以下问题：

无序集合的中位数是这样一个元素，即小于中位数的元素数量在大于中位数的元素之一内，假设没有关系。

(a) 编写一个算法，找出 3 个不同值 a、b、c 的中值。

(b) 确定您的算法在平均情况和最坏情况下进行的比较次数。

从我搜索和学习的一点点来看，这似乎被称为找到未排序数组的第k个元素，或者找到中位数的中位数？

但是，我们还没有学会快速排序，而且我能找到的一切似乎都比这里要求我的要复杂得多。也就是说，我不完全确定我理解这个问题中提出的定义。此外，找到 3 个不同值 a、b、c 的中位数是否意味着找到一组大小为 3 的中位数？

我不一定要寻找答案。只是简单的解释或澄清。谢谢。

---

尝试#1

(a) 按照 templatetypedef 的建议，我想出了这个简单的算法来解决这个问题：

我知道这非常幼稚和丑陋，但我想不出更好的解决方案，而且这已经花费了我太多时间。

(b) 似乎最好的情况是 c < a < b 进行 2 次比较，最坏的情况是 a < c < b 进行 9 次比较？那么，平均值为 (2+9)/2，即 5 次或 6 次比较？

还是我现在太天真了？

---

尝试#2

(a) 好的，所以，按照唐的建议，我非常努力地将比较次数减少到 3。从数学上讲，我理解你的意思。从中检查并扣除其余状态就足够了a<b, b<c, a<c，但是我找不到对其进行编码的方法...这是我最好的尝试：

我看不出我能做得比这更好：

(b) 最佳情况：1 次比较。平均情况：5/2 = 2 到 3 次比较。最坏情况：5 次比较。

好点？

---

最终解决方案

感谢thang，经过一番努力，终于搞定了。我的最后一个算法是正确的，但我的计数是错误的。

(b) 最佳情况：2 次比较。平均情况：2 次比较。最坏情况：3 次比较。

设置：我有一堆建于不同年份的建筑物的能源使用数据。我想按 Tableau 中构建的日期分析能源使用情况。我最初的问题是样本中没有足够的建筑物来为每年设置一个健壮的集合，由此产生的输出显示出大量的噪音。分布向右倾斜，因为有许多高异常值，但没有接近 0 的异常值，所以我想使用中值来减少少数（并且可能是错误的）高异常值的影响。

期望的解决方案：创建一个 5 年的“移动”或“运行”中位数，其中包括给定年份任一方向两年内的所有建筑物，以便每组都以年份为中心。

我在 Tableau 中尝试过的内容：我想使用 WINDOW_MEDIAN([ENERGY],-2,2)，但它是一个聚合函数。所以我尝试了 WINDOW_MEDIAN(MEDIAN([ENERGY],-2,2)。不幸的是，这给了我 5 个中位数的中位数（Median-of-Medians？！嘘！）。同样，我希望中位数为每个 5 年窗口中显示的所有单个建筑物（非汇总中位数）。

关于如何做到这一点的任何想法？谢谢！

下面是我试图理解中位数算法中位数的代码（使用大小为 5 的块）。我了解如何获得输入的中位数，但我不确定如何对块进行编码以继续递归输入，直到我只有中位数。然后在得到那个中值之后，我不知道如何用它作为一个支点来丢弃无用的信息来划分输入。getMediansArray返回大小为 ceil(input.length/5) 的数组，并getMedians仅返回数组的中位数（仅用于长度 <= 5 的数组）。

我正在使用 Medians 枢轴方法的 Median 实现一个 select-kth 算法。具体来说，我正在遵循此处列出的伪代码。. 但是，我的代码崩溃（下面讨论的错误），我明白它为什么会崩溃，但我不明白我能做些什么。

错误

原因
在 wiki 链接中，该方法select将返回一个值if left == right。但是，当从 的 return 语句调用相互递归时pivot，这意味着它将一个值（而不是索引）返回给父级，并且父级将该值设置为pivotIndex.

编码

我完全理解为什么我的代码不起作用，我只是不明白如何修复它，因为它看起来正是算法指定的。非常感谢指针！