5个sorting数组的中值
我试图find5个sorting数组的中位数的解决scheme。 这是一个面试问题。
我能想到的解决scheme是合并5个数组，然后find中位数[O（1 + m + n + o + p）]。
我知道，对于2个相同大小的sorting数组，我们可以在log（2n）中完成。 [通过比较两个数组的中位数，然后抛出每个数组的一半并重复该过程]。 寻找中位数可以是在sorting数组中的常量时间..所以我认为这不是log（n）？ ..这是什么时间的复杂性？
1]是否有一个类似的解决scheme5arrays。 如果arrays的大小相同，那么是否有更好的解决scheme呢？
2]我假设，因为这是要求5，会有一些解决scheme的Nsorting数组？
感谢任何指针。
我向面试官提出了一些澄清/问题：
是相同长度的数组
=>没有
我想在数组的值会有重叠
=>是的
作为一个练习，我认为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 …这似乎不正确？
sorting元素的合并=> [2,3,4,7,8,9,15] =>预期中值= 7
（这是对两个数组的概念的一个概括。）
如果从五个数组中的五个中间值开始，显然整体中值必须在五个中值的最小值和最大值之间。
certificate是这样的：如果a是中值的最小值，b是中值的最大值，那么每个数组的元素less于一半，小于一半的元素大于b。 结果如下。
所以在包含a的数组中，扔掉小于a的数字; 在包含b的数组中，扔掉大于b的数字…但是只丢弃两个数组中相同数量的元素。
也就是说，如果a是从数组开始的j个元素，b是数组末尾的k个元素，则抛弃数组中的第一个min（j，k）元素，最后一个min（j，k ）来自b的数组元素。
迭代，直到你总共达到1或2个元素。
这些操作中的每一个（即查找sorting数组的中位数并从数组的开始或结束处丢弃k个元素）是恒定时间。 所以每次迭代都是恒定的。
每个迭代从至less一个数组中抛出（超过）一半的元素，并且对于五个数组中的每一个只能执行log（n）次…所以整个algorithm是log（n）。
[更新]
正如Himadri Choudhury在评论中指出的那样，我的解决办法是不完整的。 有很多细节和angular落的情况下担心。 所以，为了充实一点…
对于五个数组R中的每一个，将其“中值下限”定义为R [n / 2-1]，将其“中值中值”定义为R [n / 2]，其中n是数组中元素的个数从0开始索引，除以2舍去）。
让“a”是最小的中位数，“b”是最大的中位数。 如果有多个数组的中值较低和/或多个数组的中位数最大，请从不同的数组中selecta和b（这是这种情况之一）。
现在，借用Himadri的build议：从数组中删除所有包含 a的元素， 以及从数组到b的所有元素， 并注意从两个数组中删除相同数量的元素。 请注意，a和b可以在同一个数组中; 但是如果是这样的话，他们不可能有相同的价值，否则我们可以从一个不同的数组中select其中的一个。 所以，如果这个步骤是从同一个数组的开始和结束扔掉元素，那么就可以了。
迭代只要你有三个或更多的数组。 但是，一旦你只有一两个arrays，你必须改变你的策略是排他性的，而不是包容性的; 你只能删除， 但不包括一个和以下但不包括 b。 继续这样做，只要剩下的一个或两个数组至less有三个元素（保证你有进展）。
最后，你会减less几个例子，其中最棘手的是两个数组，其中之一有一个或两个元素。 现在，如果我问你：“给定一个sorting的数组加上一两个额外的元素，find所有元素的中位数”，我想你可以在不变的时间这样做。 （同样，还有一些细节需要解决，但基本的想法是，向arrays中添加一个或两个元素并不会“非常地推动中间值”）。
你不需要做5个数组的完全合并。 你可以做一个合并sorting，直到你有（l + n + o + p + q）/ 2个元素，那么你有中间值。
应该是相当直接适用于5arrays相同的想法。
首先，将问题转换为更一般的问题。 在N个sorting的数组中find第K个元素
-
在二元search的每个sorting数组中查找（K / N）个元素，比如K1，K2 … KN
-
Kmin = min（K1 … KN），Kmax = max（K1 … KN）
-
扔掉所有小于Kmin或大于Kmax的元素，说X元素已经被扔掉了。
-
现在通过在剩余元素的sorting数组中查找第（K-X）个元素来重复这个过程
