5个排序数组的中位数

（这是您对两个数组的想法的概括。）

如果您先查看五个数组的五个中位数，则显然总中位数必须介于五个中位数中的最小和最大之间。

证明是这样的：如果a是中位数的最小值，b是中位数的最大值，则每个数组的元素小于a的一半小于元素，而元素大于b的元素小于一半。结果如下。

因此，在包含a的数组中，丢弃小于a的数字；在包含b的数组中，丢弃大于b的数字…但仅丢弃两个数组中相同数量的元素。

也就是说，如果a从其数组的开头是j个元素，而b从其数组的末尾是k个元素，则丢弃a的数组中的第一个min（j，k）个元素和最后一个min（j，k）
）b数组中的元素。

进行迭代，直到总数减少到1或2个元素。

这些 *** 作中的每个 *** 作（即，找到排序数组的中位数并从数组的开头或结尾扔掉k个元素）都是恒定时间。因此，每次迭代都是恒定时间。

每次迭代都会从至少一个数组中丢弃（超过）一半的元素，并且您只能对五个数组中的每个数组进行log（n）次…因此，总体算法为log（n）。

[更新]

正如Himadri Choudhury在评论中指出的那样，我的解决方案是不完整的。有很多细节和烦恼的案例。所以要充实一点…

对于五个数组R中的每一个，将其“较低中位数”定义为R [n / 2-1]，将其“较高中位数”定义为R [n /
2]，其中n是数组（和数组）中元素的数量从0开始索引，再向下除以2舍入）。

假设“ a”是较低中位数的最小值，而“
b”是较高中位数的最大值。如果存在多个具有最低中位数的数组和/或具有最大中位数最大的数组，请从不同的数组中选择a和b（这是其中一种极端情况）。

现在，借用Himadri的建议：删除所有元素，直到 并包括 一个从它的阵列，和向下的所有元素 ，并包括
b。从它的阵列，小心取出相同数量从两个数组中的元素。注意a和b可以在同一数组中；但是如果是这样，它们就不能具有相同的值，因为否则我们将能够从不同的数组中选择它们之一。因此，如果这一步结束时从同一数组的开头和结尾扔掉元素，就可以了。

只要有三个或更多数组，就进行迭代。但是，一旦您只剩下一两个数组，就必须将策略更改为互斥而不是互斥。您最多只能擦除 但不包括 a，向下擦除 但不包括
b。只要剩余的一个或两个数组都至少具有三个元素，就可以像这样继续 *** 作（确保您有所进步）。

最后，您将减少几种情况，其中最棘手的是剩下两个数组，其中一个数组包含一个或两个元素。现在，如果我问你：“给出一个排序的数组加上一个或两个其他元素，找到所有元素的中位数”，我想你可以在固定时间内做到这一点。（同样，有很多细节需要敲定，但是基本思想是向数组中添加一个或两个元素并不会“将中间值推入”太多。）