algorithm - 如何计算数组中的最大中位数

Question

这是一道算法题:

输入是一个包含不重复的正整数的数组。找到一个具有最大中值的连续子数组(size > 1)。

示例:输入:[100, 1, 99, 2, 1000]，输出应为 (1000 + 2)/2 = 501

我可以想出蛮力解决方案:尝试从 2 -> 数组大小的所有长度来找到最大中位数。但似乎太慢了。我也尝试在这个问题上使用两个指针，但不确定何时左右移动指针。

谁有更好的办法来解决这个问题？

Answer 1

tl;dr - 我们可以证明答案的长度必须为 2 或 3，之后是检查所有可能性的线性时间。

假设输入是A，具有最大中位数的最小子数组是a。最大的中值要么是单个元素，要么是 a 中一对元素的平均值。请注意，a 中大于中位数最大元素的每个元素只能紧挨着小于中位数最小元素的元素(否则可以选择这样的一对作为子数组以形成更大的中位数)。

如果 a 的任一端有一对元素不包含中位数的元素，则可以从 a 中删除它而不影响中位数，a矛盾。

如果 a 的任一端小于中位数的最小元素，则消除它会增加中位数，这是矛盾的。

因此 a 的每一端要么是中位数的一个元素，要么大于中位数的最大元素(因为它大于中位数的最小元素并且不等于中位数的最大元素中位数)。

因此 a 的每一端都是中位数的一个元素，否则，我们将有一个比中位数的元素更大的元素与中位数的 elt 相邻，从而形成更大的中位数。

如果 a 是奇数，那么它的长度一定是三，因为任何更大的奇数长度都可以从距离中位数最远的 a 的末尾移除 2 而不会改变中位数。

如果 a 是偶数，则它的长度必须为 2，因为任何更大的偶数长度由中位数的元素书尾，内部元素在小于和大于中位数之间交替必须具有中位数之一相邻元素比中位数的另一个元素更大，形成更大的中位数。

这个证明大纲可能需要一些编辑，但无论如何，结论是包含最大中位数的最小数组的长度必须为 2 或 3。

鉴于此，在线性时间内检查每个这样的子数组。 O(n).