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

因此，您有n个排序数组（长度不一定相等），并且要返回组合数组中第k个最小的元素（即，通过合并所有n个排序数组而形成的组合数组）

我已经尝试它及其其他变体已有相当长的时间了，直到现在，我只对以下情况感到满意：两个长度相等的数组，两个数组都已排序并且一个必须返回这两个数组的中值。这具有对数时间复杂度。

在此之后，我尝试将其概括为找到两个排序数组中最小的kth个。这是关于SO的问题。即使在这里，给出的解决方案对我也不是显而易见的。但是，即使我设法使自己相信这种解决方案，我仍然对如何解决绝对一般情况感到好奇（这是我的问题）

有人可以逐步解释我的解决方案（我认为这又应该是对数时间，即O（log（n 1）+ log（n 2）… + log（n N），其中n 1，n 2 ..

.n N是n个数组的长度），它是从更特殊的情况开始并发展到更一般的情况？

我知道互联网上遍布着针对更具体案例的类似问题，但是我还没有找到令人信服和明确的答案。

这是一个指向SO的问题（及其答案）的链接，该问题处理5个排序的数组并找到组合数组的中位数。答案太复杂了，我无法一概而论。

即使是针对更具体情况的干净方法（如我在帖子中提到的那样）也是受欢迎的。

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

PPS：这不是家庭作业的问题，我只是在准备面试。

这不会泛化链接，但是可以解决问题：

当达到每个数组只有一个元素（或0）的程度时，请使用这些数据制作一个大小为n的新数组，然后排序并选择第k个元素。

由于始终保证至少要删除一个数组的一半，因此在 N 次迭代中，您将摆脱掉一半的元素。这意味着有 N个log k 次迭代。每次迭代的阶数为 N

log k （由于二进制搜索），所以整个事情是 N ^ 2（log k）^ 2

当然，这是最糟糕的情况，基于这样的假设：您只去除了一半最大数组，而不是其他数组。实际上，我认为典型的性能要比最差的情况好很多。