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

Question

这是一道算法题：

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

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

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

谁有解决这个问题的更好主意？

Answer 1

这是解决O(n)中问题的算法的Python实现：

import random
import statistics

n = 50
numbers = random.sample(range(n),n)

max_m = 0;
max_a = [];

for i in range(2,3):
    for j in range(0,n-i+1):
        a = numbers[j:j+i]
        m = statistics.median(a)
        if m > max_m:
            max_m = m
            max_a = a

print(numbers)
print(max_m)
print(max_a)

这是仅搜索长度为 2 或 3 的子数组的蛮力算法 (O(n^3)) 的变体。原因是对于每个大小为 n，存在一个具有相同或改进的中位数的子数组。递归地应用这个推理，我们可以将子数组的大小减少到 2 或 3。因此，通过只查看大小为 2 或 3 的子数组，我们可以保证获得具有最大中位数的子数组。

操作如下：如果对于一个连续的子数组（在开头或结尾），至少有一半的元素低于中位数（或低于构成中位数的两个值，如果是这种情况），删除它们以改善或至少保留中位数。

如果在所有子数组中总是有至少一个大于或等于中位数的元素比下面的元素多，那么会出现一个点，子数组的大小将是中位数的大小.在那种情况下，这意味着补码将有更多的元素低于中位数，因此，我们可以简单地删除补码并改进（或保留）中位数。因此，我们始终可以执行该操作。对于n=3，可能需要移除2个或3个元素才能执行操作，这是不允许的。在这种情况下，结果就是列表本身。

Answer 2

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

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

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

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

因此a的每一端要么是中位数的一个元素，要么大于中位数的最大元素（因为它大于中位数的最小元素而不等于中位数的最大元素中位数）。

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

如果 a 是奇数，那么它的长度必须是三，因为任何更大的奇数长度都可以在不改变中位数的情况下从离中位数最远的 a 的末尾移除 2。

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

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

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

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

How to calculate the maximum median in an array

algorithm

math

median