在k个数组中寻找第h到b个最小元素的有效方法

Question

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

存在长度m的数的k未排序数组。目标是在给定a<；b<；m的情况下，以一种高效且内存保守的方式在k数组中找到a-th到b-th的最小元素。在接下来的问题中，MySQL数据库中的“未排序数组”被改为跨不同表的列，可以使用什么样的高效数据结构，相应的检索算法是什么。你知道吗

我提出了两种可能的解决方案：

第一：暴力：

1. 首先使用quickselect查找每个数组的第b个最小元素。你知道吗
2. 然后找到小于每个数组的b-th元素的元素，并将它们存储到大小k*bb-treeC中。你知道吗
3. 然后在C中找到a-th到b-th的最小元素。你知道吗

对于使用quickselect查找b-th最小元素的第一步，平均时间总共是从O（km）到O（km*log（m））。步骤2时间复杂度为O（km）。最后一步是找出a-th和b-th之间的元素，取O（（b-a）log（kb））。所以total在时间上需要O（km）到O（km*log（m））+O（（b-a）log（kb）），在空间上需要O（kb）。你知道吗

秒：递归地弹出最小的元素

对于每个循环，执行

1. 找到所有k数组的最小元素，存储在B树C
2. 在C中找到最小的元素，并从C中弹出该元素，然后从数组中找到它。你知道吗
3. 重复操作，直到弹出a-1数字，然后转到4
4. 存储a到b之间的值，同时重复1到2

因此计算复杂度为O（k*log（k））+O（b*log（k）），空间复杂度为O（max（k，b-a））。这似乎是最小的空间复杂性。你知道吗

有什么更有效的方法可以做到这一点？特别是quickselect的最坏情况是O（n^2），它看起来太大了，而对于b=m/2，在空间上的中位数O（kb），或者在时间上的O（b*log（k））被认为太大了。对于MySQL数据库，我建议在解决方案1中使用B-tree，它在空间和时间上都有O（kb）的情况下，对数据库进行k查询。而在解决方案2中，据说b查询到MySQL数据库太大，b树插入是O（log（m）），其中m可能非常大。你知道吗

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堆。然后，对于每一个其他项，如果它小于堆上最大的项，则用新项移除堆上最大的项。你知道吗

处理完所有km项后，最小的b项在堆上，由于它是最大堆，因此您弹出的第一个b-a项将是所有k数组中的a^th到b^th项。你知道吗

// 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（b）额外内存，第一个循环为O（kmlogb），第二个循环为O（blogb）。你知道吗

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

另一种可能性。对每个k数组运行buildheap方法。也就是0（公里）。然后进行合并以选择第一个b项。合并需要：

• O（logm）从源数组中删除每个项
• O（logb）将每个项添加到合并堆
• O（logb）从合并堆中删除每个项

第二步是O（b*（logm+logb+logb））。你知道吗

这样就得到了O（km+b*（logm+logb+logb）），您将使用O（b）额外的内存。这是否会比最初的建议更快是值得怀疑的。这取决于b和m之间的关系。b的值越大，速度越慢。而且代码编写起来要复杂得多。你知道吗