我试图找到5个排序数组中位数的解决方案。这是一次面试的问题。
我能想到的解决方案是合并5个数组，然后找到中位数[O（l + m + n + o + p）]。
我知道对于相同大小的2个排序数组，我们可以在log（2n）中进行。[通过比较两个数组的中位数，然后扔掉每个数组的一半并重复该过程]。..在排序数组中查找中位数可以是恒定时间..所以我认为这不是log（n）吗？..这的时间复杂度是多少？
1]是否有针对5个数组的类似解决方案。如果数组大小相同怎么办，有没有更好的解决方案呢？
2]我假设既然要求5，那么对N个排序的数组会有一些解决方案吗？
感谢您的指导。
我向面试官问了一些澄清/问题： 数组的长度是否相同 =>否， 我想数组的值会重叠 =>是
作为练习，我认为2个数组的逻辑不会扩展。尝试一下： 将上述2个数组的逻辑应用于3个数组：[3,7,9] [4,8,15] [2,3,9] …中位数7,8,3 抛出元素[ 3,7,9] [4,8] [3,9] ..中位数7,6,6 抛出元素[3,7] [8] [9] ..中位数5,8,9 … 抛出元素[7] [8] [9] ..中位数= 8 …这似乎不正确吗？
已排序元素的合并=> [2,3,4,7,8,9,15] =>预期中位数= 7
（这是您对两个数组的想法的概括。）
如果您先查看五个数组的五个中位数，则显然总中位数必须介于五个中位数中的最小和最大之间。
证明是这样的：如果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。只要剩余的一个或两个数组都至少具有三个元素，就可以像这样继续操作（确保您有所进步）。
最后，您将减少几种情况，其中最棘手的是剩下两个数组，其中一个数组包含一个或两个元素。现在，如果我问你：“给出一个排序的数组加上一个或两个其他元素，找到所有元素的中位数”，我想你可以在固定时间内做到这一点。（同样，有很多细节需要敲定，但是基本思想是向数组中添加一个或两个元素并不会“将中间值推入”太多。）
