5个排序数组的中位数 [英] Median of 5 sorted arrays

问题描述

我正在尝试找到 5 个已排序数组的中位数的解决方案.这是一道面试题.

I am trying to find the solution for median of 5 sorted arrays. This was an interview questions.

我能想到的解决方案是合并 5 个数组，然后找到中位数 [O(l+m+n+o+p)].

The solution I could think of was merge the 5 arrays and then find the median [O(l+m+n+o+p)].

我知道对于 2 个相同大小的排序数组，我们可以在 log(2n) 中完成.[通过比较两个数组的中位数，然后丢弃每个数组的一半并重复该过程]... 在排序数组中找到中位数可以是常数时间.. 所以我认为这不是 log(n) ?.. 时间复杂度是多少?

I know that for 2 sorted arrays of same size we can do it in log(2n). [by comparing the median of both arrays and then throwing out 1 half of each array and repeating the process]. .. Finding median can be constant time in sorted arrays .. so I think this is not log(n) ? .. what is the time complexity for this ?

1] 5 个数组是否有类似的解决方案.如果数组大小相同，那么有没有更好的解决方案呢?

1] Is there a similar solution for 5 arrays . What if the arrays are of same size , is there a better solution then ?

2] 我假设既然要求 5，那么 N 个排序数组会有一些解决方案吗?

2] I assume since this was asked for 5, there would be some solution for N sorted arrays ?

感谢您的指点.

我向面试官提出的一些澄清/问题:
数组的长度是否相同
=> 没有
我猜数组的值会有重叠
=> 是的

Some clarification/questions I asked back to the interviewer:
Are the arrays of same length
=> No
I guess there would be an overlap in the values of arrays
=> Yes

作为练习，我认为 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 ... 这似乎不正确?

As an exercise, I think the logic for 2 arrays doesnt extend . Here is a try:
Applying the above logic of 2 arrays to say 3 arrays: [3,7,9] [4,8,15] [2,3,9] ... medians 7,8,3
throw elements [3,7,9] [4,8] [3,9] .. medians 7,6,6
throw elements [3,7] [8] [9] ..medians 5,8,9 ...
throw elements [7] [8] [9] .. median = 8 ... This doesnt seem to be correct ?

已排序元素的合并 => [2,3,4,7,8,9,15] => 预期中位数 = 7

The merge of sorted elements => [2,3,4,7,8,9,15] => expected median = 7

推荐答案

(这是您对两个数组的想法的概括.)

(This is a generalization of your idea for two arrays.)

如果您首先查看五个数组的五个中位数，显然整体中位数必须介于五个中位数中的最小和最大之间.

If you start by looking at the five medians of the five arrays, obviously the overall median must be between the smallest and the largest of the five medians.

证明是这样的:如果 a 是中位数的最小值，b 是中位数的最大值，那么每个数组少于一半的元素小于 a，少于一半的元素大于 b.结果如下.

Proof goes something like this: If a is the min of the medians, and b is the max of the medians, then each array has less than half of its elements less than a and less than half of its elements greater than b. Result follows.

所以在包含a的数组中，丢弃小于a的数字；在包含 b 的数组中，丢弃大于 b 的数字......但只丢弃两个数组中相同数量的元素.

So in the array containing a, throw away numbers less than a; in the array containing b, throw away numbers greater than b... But only throw away the same number of elements from both arrays.

也就是说，如果 a 是数组开头的 j 个元素，b 是数组结尾的 k 个元素，则丢弃 a 数组中的前 min(j,k) 个元素和最后一个 min(j,k) 来自 b 数组的元素.

That is, if a is j elements from the start of its array, and b is k elements from the end of its array, you throw away the first min(j,k) elements from a's array and the last min(j,k) elements from b's array.

迭代，直到总共减少到 1 或 2 个元素.

Iterate until you are down to 1 or 2 elements total.

这些操作中的每一个(即，查找已排序数组的中值并从数组的开头或结尾丢弃 k 个元素)都是恒定时间.所以每次迭代都是常数时间.

Each of these operations (i.e., finding median of a sorted array and throwing away k elements from the start or end of an array) is constant time. So each iteration is constant time.

每次迭代都会从至少一个数组中丢弃(超过)一半的元素，并且您只能对五个数组中的每一个执行 log(n) 次......所以整体算法是 log(n).

Each iteration throws away (more than) half the elements from at least one array, and you can only do that log(n) times for each of the five arrays... So the overall algorithm is log(n).

[更新]

正如 Himadri Choudhury 在评论中指出的那样，我的解决方案是不完整的；有很多细节和极端情况需要担心.所以，稍微充实一下……

As Himadri Choudhury points out in the comments, my solution is incomplete; there are a lot of details and corner cases to worry about. So, to flesh things out a bit...

对于五个数组 R 中的每一个，将其下中位数"定义为 R[n/2-1]，将其上中位数"定义为 R[n/2]，其中 n 是数组中的元素数(数组从 0 开始索引，除以 2 向下舍入).

For each of the five arrays R, define its "lower median" as R[n/2-1] and its "upper median" as R[n/2], where n is the number of elements in the array (and arrays are indexed from 0, and division by 2 rounds down).

设a"是下中位数中最小的，b"是上中位数中最大的.如果有多个具有最小下中位数的数组和/或多个具有最大上中位数的数组，请从不同的数组中选择 a 和 b(这是这些极端情况之一).

Let "a" be the smallest of the lower medians, and "b" be the largest of the upper medians. If there are multiple arrays with the smallest lower median and/or multiple arrays with the largest upper median, choose a and b from different arrays (this is one of those corner cases).

现在，借用 Himadri 的建议:删除数组中直到 和包括 a 的所有元素，以及从数组中删除 和包括 b 的所有元素，注意从两个数组中删除相同数量的元素.注意 a 和 b 可以在同一个数组中；但如果是这样，它们就不能具有相同的值，否则我们就可以从不同的数组中选择其中之一.所以如果这一步最终把同一个数组的开头和结尾的元素扔掉也没关系.

Now, borrowing Himadri's suggestion: Erase all elements up to and including a from its array, and all elements down to and including b from its array, taking care to remove the same number of elements from both arrays. Note that a and b could be in the same array; but if so, they could not have the same value, because otherwise we would have been able to choose one of them from a different array. So it is OK if this step winds up throwing away elements from the start and end of the same array.

只要您有三个或更多数组，就进行迭代.但是一旦你只剩下一两个数组，你就必须改变你的策略，使其成为排他性而不是包容性；您最多只能擦除但不包括 a，向下擦除但不包括 b.就这样继续下去，只要剩下的一两个数组都至少有三个元素(保证你进步).

Iterate as long as you have three or more arrays. But once you are down to just one or two arrays, you have to change your strategy to be exclusive instead of inclusive; you only erase up to but not including a and down to but not including b. Continue like this as long as both of the remaining one or two arrays has at least three elements (guaranteeing you make progress).

最后，您将减少到几种情况，其中最棘手的是剩余两个数组，其中一个具有一两个元素.现在，如果我问你:给定一个排序数组加上一两个附加元素，找到所有元素的中位数"，我认为你可以在恒定时间内做到这一点.(同样，有很多细节需要敲定，但基本思想是将一两个元素添加到数组中并不会推动中位数".)

Finally, you will reduce to a few cases, the trickiest of which is two arrays remaining, one of which has one or two elements. Now, if I asked you: "Given a sorted array plus one or two additional elements, find the median of all elements", I think you can do that in constant time. (Again, there are a bunch of details to hammer out, but the basic idea is that adding one or two elements to an array does not "push the median around" very much.)

这篇关于5个排序数组的中位数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！