arrays - 从 n 个排序数组中找到第 k 个最小的数字

Question

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

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

在此之后，我尝试将其概括为在两个排序数组中找到第 k 个最小的数组。 Here是关于SO的问题。即使在这里，给出的解决方案对我来说也不明显。但即使我以某种方式设法说服自己接受这个解决方案，我仍然很好奇如何解决绝对一般情况(这是我的问题)

有人能给我解释一下一步一步的解决方案吗(我认为这又应该花费对数时间，即 O( log(n₁) + log(n₂) ... + log(n_N) 其中 n₁, n₂...n_N 是n 个数组的长度)从更具体的情况开始，然后移动到更一般的情况？

我知道互联网上到处都是关于更具体案例的类似问题，但我还没有找到令人信服和明确的答案。

Here 是指向 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，在您找到的拆分点处截断所有数组并迭代较小的数组(使用上半部分，并搜索元素 (k-L)。

当你到达每个数组只有一个元素(或 0)的地步时，用这些数据创建一个大小为 n 的新数组，排序，然后选择第 k 个元素。

因为您总是保证至少删除一个数组的一半，所以在 N 次迭代中，您将删除一半的元素。这意味着有 N log k 次迭代。每次迭代都是 N log k 的顺序(由于二进制搜索)，所以整个事情是 N^2 (log k)^2 这就是全部，当然，最坏的情况，假设你只去掉了最大数组的一半，而不是其他数组。在实践中，我想典型的性能会比最坏的情况好很多。