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

Question

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

algorithmmathmedian

6

这是一个算法问题：

输入为一个非重复正整数数组。寻找一个连续的子数组（长度大于1），其中包含最大的中位数。

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

我可以想出一种暴力解法：尝试所有长度从2到数组大小来寻找最大的中位数。但这看起来太慢了。我也尝试过在这个问题上使用双指针，但不确定何时移动左右指针。

是否有更好的解决方法来解决这个问题？

- CipherText

1

你能提供一个例子吗？据我所知，取一个包含最大元素的长度为2的子数组就足够了，但也许比我想象的更复杂。 - Gilles-Philippe Paillé

1

通过使用暴力算法进行一些测试，似乎它总是针对包含2或3个元素的数组，而不一定包含最大元素。但也可能有一些例外... 例如：数组=[4,5,6,1,9,2,3,8,0,7]，最大中位数子数组：[8,0,7]，中位数：7。 - Gilles-Philippe Paillé

@Gilles-PhilippePaillé。刚刚添加了一个例子。您发现的东西真的很有趣。我还没有实施暴力破解，但我尝试了许多例子，似乎大小始终小于3。不确定是否有一种方法可以证明这一点？ - CipherText

3

请问你需要寻找的是“中位数”还是“平均数”？问题中提到了“中位数”，但示例给出的是计算得出的“平均数”值。 - Anders Lindahl

2

@Anders：给定两个数字，它们的平均数和中位数总是相同的。 - Andreas Rejbrand

显示剩余3条评论

2个回答

2

这是一个用Python实现的算法，可以在O(n)时间内解决问题。原始答案被翻译成了“最初的回答”。

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)

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

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

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

- Gilles-Philippe Paillé

谢谢您的答复！时间复杂度应该大于O(n^2)，因为statistics.median(a)应该需要超过O(N)的时间。不确定是否可以通过反证法证明答案的长度应该始终为2或3。 - CipherText

是的，我知道快速选择在平均情况下可以达到O(N)。但是for i in range(2,n):是O(N)，for j in range(0,n-i+1):也是O(N)，m = statistics.median(a)也是O(N)。因此总体时间复杂度应该大约为O(N^3)。无论如何，我认为你对长度为2或3的想法是正确的，尽管我也找不到数学证明。感谢你的回答！ - CipherText

哦，你说的 O(n^3) 是对的。我会编辑我的回答。 - Gilles-Philippe Paillé

我不确定你的证明是否有意义。根据定义，每个子数组在中位数上方和下方都有相同数量的元素。 - Dave

@Dave，我表述不正确。我真正的意思是“大于或等于中位数”，因此数组并没有完全分成两半。 - Gilles-Philippe Paillé

显示剩余2条评论

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Dave · Accepted Answer

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

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

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

如果a的任一端小于中位数最小元素，那么将其消除会增加中位数，这也是矛盾的。

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

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

如果a是奇数，则它必须是长度为三，因为任何更大的奇数长度可以将2从离中位数最远的a末端删除而不改变中位数。

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

综上所述，包含最大中位数的最小数组必须为长度为2或3。

有了这个结论之后，就可以在线性时间内检查每个这样的子数组。O(n)。