查找第k个最小的数从n个分类的数组 [英] Finding kth smallest number from n sorted arrays

问题描述

所以，你有n个排序的数组（长度相等不一定），并且你要返回第k个最小元素的组合阵列（即通过合并所有N个组合形成的数组排序数组）

So, you have n sorted arrays (not necessarily of equal length), and you are to return the kth smallest element in the combined array (i.e the combined array formed by merging all the n sorted arrays)

我一直在尝试它和它的其他变种相当长的一段时间了，而且到现在为止我只觉得在这样舒适的地方有两个数组长度相等，两者排序，一个人回到这两个的中间值。 这具有对数时间复杂度。

I have been trying it and its other variants for quite a while now, and till now I only feel comfortable in the case where there are two arrays of equal length, both sorted and one has to return the median of these two. This has logarithmic time complexity.

在此我试图将其推广到第k个最小发现两个已排序的阵列中。 <一href="http://stackoverflow.com/questions/4607945/how-to-find-the-kth-smallest-element-in-the-union-of-two-sorted-arrays">Here是这样的问题。 即使在这里给出的解决方案是不明显我。但是，即使我以某种方式设法说服该解决方案的我自己，我还是好奇，怎么解决绝对一般的情况下（这是我的问题）

After this I tried to generalize it to finding kth smallest among two sorted arrays. Here is the question on SO. Even here the solution given is not obvious to me. But even if I somehow manage to convince myself of this solution, I am still curious as to how to solve the absolute general case (which is my question)

有人可以解释我一步一步的解决方案（而这又在我看来，应该采取对数时间，即O（日志（N ₁ ）+的log（n ₂ ） ... +的log（n <子> N ），其中n ₁ ，N ₂ ... N <子> N 是在n阵列的长度），其开始从更具体的情况下，并转移到更一般的一个？

Can somebody explain me a step by step solution (which again in my opinion should take logarithmic time i.e O( log(n₁) + log(n₂) ... + log(n_N) where n₁, n₂...n_N are the lengths of the n arrays) which starts from the more specific cases and moves on to the more general one?

我知道类似的问题更具体的情况下，有没有在互联网上，但我还没有找到一个有说服力的和明确的答案。

I know similar questions for more specific cases are there all over the internet, but I haven't found a convincing and clear answer.

这里是SO链接到一个问题（和答案），这用5排序阵列和发现合并的阵列的中位数的交易。只是变得太复杂，我能回答概括它。

Here is a link to a question (and its answer) on SO which deals with 5 sorted arrays and finding the median of the combined array. The answer just gets too complicated for me to able to generalize it.

即使清洁方法的更具体情况（如我的帖子中提到的）的欢迎。

Even clean approaches for the more specific cases (as I mentioned during the post) are welcome.

PS：你是否认为这可以进一步推广到无序阵列的情况下

PS: Do you think this can be further generalized to the case of unsorted arrays?

PPS：这不是一个家庭作业的问题，我只是preparing面试

PPS: It's not a homework problem, I am just preparing for interviews.

推荐答案

这也不能一概而论的联系，但不解决问题：

This doesn't generalize the links, but does solve the problem:

1. 在仔细检查所有的数组，如果任何有长度> K，截断长度K（这是愚蠢的，但我们会乱用K后，所以做吧）
2. 确定现存最大的阵列A.如果不止一个，挑一个。
3. 选择中间元素的最大数组A并购。
4. 使用二进制搜索在剩余的阵列找到相同的元素（或最大的元素＆lt; = M）。
5. 根据各种要素的指标，计算元素＆总数LT = M和> M.这应该给你两个数字：L，数量和LT = M和G，数量> M
6. 如果K＆LT; L，截断所有阵列，在你找到的分割点和重复的小阵列（使用下半部）。
7. 如果K> L，截断所有阵列，在你找到的分割点和重复的小阵列（使用上半部，并搜索元素（KL）。

当你到达的地步，你只需要每个数组一个元素（或0），使大小为n的一个新的数组这些数据，排序，并选择第k个元素。

When you get to the point where you only have one element per array (or 0), make a new array of size n with those data, sort, and pick the kth element.

由于你总是保证删除一个阵列中的至少一半，在 N 的迭代，你会摆脱一半的元素。这意味着还有的 N日志氏/ em>的迭代。每次迭代是秩序的 N日志氏/ em>的（由于二进制搜索），所以整件事的 N ^ 2（日志K）^ 2 的这一切当然，最坏的情况下，根据您只有摆脱没有另一半的阵列最大阵列的，假设。在实践中，我想象中的典型性能会比最坏的情况相当好一点。

Because you're always guaranteed to remove at least half of one array, in N iterations, you'll get rid of half the elements. That means there are N log k iterations. Each iteration is of order N log k (due to the binary searches), so the whole thing is N^2 (log k)^2 That's all, of course, worst case, based on the assumption that you only get rid of half of the largest array, not of the other arrays. In practice, I imagine the typical performance would be quite a bit better than the worst case.

这篇关于查找第k个最小的数从n个分类的数组的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！