我正在尝试找到 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] ..medians 5,8,9 ...
throw elements [7] [8] [9] .. median = 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 的建议:从其数组中删除 和包括 a 的所有元素，以及从其数组中删除 和包括 b 的所有元素，注意从两个数组中删除相同数量的元素。请注意，a 和 b 可以在同一个数组中；但如果是这样，它们就不能具有相同的值，否则我们就可以从不同的数组中选择其中一个。因此，如果此步骤最终丢弃同一数组开头和结尾的元素，那也没关系。
只要你有三个或更多数组，就进行迭代。但是一旦你只剩下一个或两个阵列，你就必须改变你的策略以排他性而不是包容性；您最多只能删除但不包括 a 和但不包括 b。继续这样下去，只要剩下的一两个数组都至少有三个元素(保证你取得进步)。
最后，你会减少到几种情况，其中最棘手的是剩下两个数组，其中一个有一个或两个元素。现在，如果我问你:“给定一个排序数组加上一两个附加元素，找到所有元素的中位数”，我认为你可以在常数时间内完成。 (同样，有很多细节需要敲定，但基本思想是向数组添加一个或两个元素不会“插入中位数”太多。)
关于arrays - 5 个排序数组的中位数，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/6182488/