algorithm - 如何对 m x n 矩阵进行排序，该矩阵的所有 m 行和 n 列都已排序？

Question

给定一个 m 行 n 列的矩阵，每个矩阵都已排序。如何高效地对整个矩阵进行排序？

我知道一个运行复杂度为 O(m n log(min(m,n)) 的解决方案。我正在寻找更好的解决方案。

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

这是一个例子:

[[1,4,7,10],

 [2,5,8,11],

 [3,6,9,12]]

是对每一行和每一列进行排序的输入矩阵。

预期输出是:

[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

我不认为你可以比 Ω(m n log(min(m, n)) 更快地完成它，在至少在一般情况下不是。

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

每个圆都是一个矩阵项，每个箭头表示已知的顺序关系(箭头源头的项小于箭头目的地的项)。

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

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

2 Σ_{k < m} Ω(k log k) + (n - m + 1) Ω(m log m)

= 2 Ω(m² log m) + (n - m + 1) Ω(m log m)

= Ω(m n log m)