假设我有 K 个长度为 L 的数组 A1 到 AK 。我想在不使用太多辅助空间的情况下合并内存中的这些数组，以便我得到以下形式的最终输出 smallest L elements are present in A1 next Lsmallest in A2 等等 。基于最小优先级队列的算法需要额外的 L*K 空间用于输出数组。 L*K 约为 10 亿
最佳答案
您可以在 O(n log k) 时间和 O(1) 辅助空间中就地合并 k 个总长度为 n 的排序数组。时间复杂度等于使用堆的异地解决方案。
文章 Multiway in-place merging 中描述了该算法作者:Geffert 和 Gajdoš (2010):
We present an algorithm for asymptotically efficient k-way merging. Given an array A containing k sorted subsequences A_1, ..., A_k of respective lengths n_1, ..., n_k, where Σ n_i = n, our algorithm merges A_1, ..., A_k into a single sorted sequence in-place and in linear time, performing c_k·n + o(n) element comparisons and 3·n + o(n) element moves, where c_k = ⌊lg k⌋ + 2⋅(1 − 2⌊lg k⌋/k), which is a constant satisfying lg k ≤ c_k ≤ ⌈lg k⌉ and, moreover, bounded by c_k ≤ lg k + 0.0861. The algorithm does not merge stably, however, it does not require that the elements in A are all distinct.
关于algorithm - 是否有一些有效的算法可以在 O(1) 额外空间或最小额外空间中合并 k 个排序数组，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/59108349/