求k个阵列中第a到第b个最小元素的有效方法

Question

我最近接受了一家社交媒体公司的面试，在那里我被问到了以下问题。

有k个长度为m的未排序数组。目标是在给定a mysql数据库中的“未排序数组”改为跨不同表的列，可以使用哪些高效的数据结构以及相应的检索算法。<>

我提出了两个可能的解决方案:

null

对于使用quickselect查找第b个最小元素的第一步，平均时间总共从O(km)到O(km*log(m))。第二步时间复杂度为O（km）。最后一步是在C中的第a和第b个最小元素之间寻找元素，取O（（b-a）log(kb))。因此，total在时间上需要O（km）到O（km*log(m))+O（（b-a）log(kb))，在空间上需要O（kb）。

第二：递归地弹出最小的元素

对于每个循环，请执行

null

Answer 1

一种简单的方法是创建大小为B的最大堆。然后运行以下代码：

for arr in arrays // process each of the k arrays in turn
    for i = 0 to length(k)-1
        if heap.count < b
            heap.push(arr[i])
        else if (arr[i] < heap.peek())
            heap.pop()
            heap.push(arr[i])

这里的想法是用前b项填充max-heap。然后，对于每一个其他项，如果它小于堆中最大的项，则用新项移除堆中最大的项。

当您处理完所有km项时，最小的b项位于堆中，并且由于它是一个最大堆，您弹出的第一个b-a项将是所有k数组中的第a到第b项。

// all items have been processed, take the first *b - a* items from the max heap
for i = 0 to (b-a-1)
   result[i] = heap.pop()

最坏的情况是第一个循环为O（km log b)，第二个循环为O（b log b)，使用O(b)额外的内存。

如果允许销毁源数组，可以编写自定义的quickselect，将k个数组作为单个数组进行索引。这将是O(km)，使用O(k)额外的内存作为间接索引。缺点是索引代码会慢一些。当然，这些项会在数组之间移动。您可能需要O(b)额外的内存来存储返回值。渐近地说，它比我最初的选择更有效。它是否会跑得更快完全是另一个问题。

另一种可能性。在每个k个数组上运行build-heap方法。那是O（公里）。然后进行合并以选择前b项。合并需要：

• o（log m）从源数组中移除每个项
• o（日志b）将每个项添加到合并堆
• o（html" target="_blank">日志b）从合并堆中移除每个项

第二步是O(b*(log m+log b+log b))。

这就给出了O(km+b*(log m+log b+log b))，并且您将使用O(b)额外的内存。这是否会比最初的建议更快还值得怀疑。它取决于b和M之间的关系。b的值越大，这就越不可能更快。代码编写起来要复杂得多。