如何对amxn矩阵进行排序,其中m行的所有排序和n列排序？

Question

给定具有m行和n列的矩阵,每个列都被排序.如何有效地整理整个矩阵？

我知道一个在O(mn log(min(m,n))中运行的解决方案.我正在寻找更好的解决方案.

我知道的方法一次基本上需要2行/列并应用合并操作.

这是一个例子:

[[1,4,7,10],

 [2,5,8,11],

 [3,6,9,12]]

是输入martix,它对每一行和每列进行排序.

预期产出是:

[1,2,3,4,5,6,7,8,9,10,11,12]

另一个例子:

[[1, 2, 3, 3, 4, 5, 6, 6, 7, 7],

 [1, 2, 4, 6, 7, 7, 8, 8, 9,10],

 [3, 3, 4, 8, 8, 9,10,11,11,12],

 [3, 3, 5, 8, 8, 9,12,12,13,14]]

Answer 1

我认为你不能比Ω(mn log(min(m,n))更快地完成它,至少在一般情况下不是这样.

假设(不失一般性)m < n.然后你的矩阵看起来像这样:

每个圆圈是一个矩阵条目,每个箭头表示一个已知的顺序关系(箭头源处的条目小于箭头目的地的条目).

要对矩阵进行排序,我们必须解决所有未知的顺序关系,其中一些显示在灰色框中:

对所有这些框进行排序需要:

2Σ _{ķ < 米} Ω(ķ日志ķ)+(ñ - 米 + 1)Ω(米日志米)

= 2Ω(米 ²日志米)+(ñ - 米 + 1)Ω(米日志米)

=Ω(mn log m)