python - 在 k 个数组中找到第 a 到第 b 个最小元素的有效方法

Question

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

有k个长度为m的未排序数组。目标是在给定a < b < m的情况下，以一种有效且内存保守的方式在k个数组中找到第a到b 个最小元素。在后续问题中，将“未排序的数组”更改为跨 MySQL 数据库中不同表的列，可以使用哪些可能的高效数据结构以及相应的检索算法是什么。

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

第一：蛮力：

1. 首先使用快速选择找到每个数组的第 b 个最小元素。
2. 然后找到小于每个数组的第 b 个元素的元素，并将它们存储到大小为k * b B-tree C中。
3. 然后在C中找到第a 到第b个最小元素。

对于使用快速选择找到第 b 个最小元素的第一步，平均时间是从O(km)到O(km * log(m)) 。步骤 2 时间复杂度为O(km)。最后一步是在C中找到第 a 和第 b 个最小元素之间的元素，取O ((ba)log(kb))。所以总需要O(km)到O(km * log(m)) + O((ba)log(kb))时间，以及O(kb)空间。

二：递归弹出最小元素

对于每个循环，执行

1. 找到所有k个数组的最小元素，存储在 B-tree C中
2. 找到C中的最小元素，并从C中弹出这个元素，并从它出现的数组中弹出。
3. 重复直到弹出a-1个数字，然后转到4
4. 存储从a到b的值，同时重复 1 到 2

因此计算复杂度为O(k * log(k)) + O(b * log(k))，空间复杂度为O(max( k , ba ))。这似乎是最小的空间复杂度。

有什么更有效的方法来做到这一点？特别是快速选择的最坏情况是O(n^2)，这似乎太大了，并且对于b = m/2正好在空间中的中位数O(kb)或时间中的O(b * log(k))被考虑太大。对于 MySQL 数据库，我建议使用 B-tree，它在解决方案 1 中提供快速排名选择，同时空间和时间仍有O(kb) ，对数据库进行k次查询。在解决方案 2 中，据说对 MySQL 数据库的 b 查询太大，B-tree 插入是O(log(m))，其中m可能非常大。

标签： pythonmysqlalgorithmsortingtime-complexity

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个项目填充一个最大堆。然后，对于每个其他项，如果它小于堆上的最大项，则使用新项删除堆上最大的项。

当您处理完所有km项目时，最小的b项目在堆上，并且由于它是最大堆，因此您弹出的第一个ba项目将是所有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) 额外内存。

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

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

• O(log m) 从源数组中删除每个项目
• O(log b) 将每个项目添加到合并堆
• O(log b) 从合并堆中删除每个项目

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

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