从n个排序数组中查找第k个最小数字

Question

所以,你有n个排序数组(不一定长度相等),你要返回组合数组中的第k个最小元素(即合并所有n个排序数组形成的组合数组)

我已经尝试了它和它的其他变种已经有一段时间了,直到现在我只觉得有两个相等长度的数组,两个都排序,一个必须返回这两个的中位数.这具有对数时间复杂度.

在此之后,我试图将其概括为在两个排序的数组中找到第k个最小的.这是关于SO的问题.即使在这里,给出的解决方案对我来说并不明显.但是,即使我莫名其妙地设法说服该解决方案的我自己,我还是好奇,怎么解决绝对一般的情况下(这是我的问题)

有人可以解释我一步一步的解决方案(我认为应该采取对数时间,即O(log(n ₁)+ log(n ₂)... + log(n _N)其中n ₁,n ₂ .. .n _N是n个数组的长度)从更具体的情况开始并转移到更一般的情况？

我知道类似的问题对于更具体的案例有互联网,但我没有找到一个令人信服和明确的答案.

这是一个关于SO的问题(及其答案)的链接,它处理5个排序的数组并找到组合数组的中位数.答案对我来说太复杂了,无法概括它.

对于更具体的案例(正如我在帖子中提到的),即使是干净的方法也是受欢迎的.

PS:你认为这可以进一步推广到未排序数组的情况吗？

PPS:这不是一个家庭作业问题,我只是准备采访.

Answer 1

这并没有概括链接,但确实解决了问题:

1. 遍历所有数组,如果有任何长度> k,截断到长度k(这是愚蠢的,但我们稍后会搞乱k,所以无论如何都要这样做)
2. 识别剩余的最大阵列A.如果不止一个,请选择一个.
3. 选择最大阵列A的中间元素M.
4. 在剩余的数组上使用二进制搜索来查找相同的元素(或最大的元素<= M).
5. 根据各种元素的索引,计算元素的总数<= M和> M.这应该给你两个数字:L,数字<= M和G,数字> M
6. 如果k <L,则截断您找到的分裂点处的所有数组,并在较小的数组上进行迭代(使用下半部分).
7. 如果k> L,则截断您找到的分裂点处的所有数组,并在较小的数组上进行迭代(使用上半部分,并搜索元素(kL)).

当你到达每个数组只有一个元素(或0)的点时,用这些数据创建一个大小为n的新数组,排序并选择第k个元素.

因为你总是保证删除一个数组的至少一半,在N次迭代中,你将摆脱一半的元素.这意味着有N log k迭代.每次迭代都是N log k的顺序(由于二进制搜索),所以整个事情是N ^ 2(log k)^ 2 这当然是最糟糕的情况,基于你只摆脱了一半的假设最大的数组,而不是其他数组.在实践中,我认为典型的性能会比最坏的情况好一点.