如何对amxn矩阵的所有m行进行排序并对n列进行排序？
给定一个有m行和n列的矩阵，每个矩阵都是排序的。 如何有效地排序整个矩阵？
我知道在O（mn 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]]
我认为你可以做得比Ω（mn log（min（m，n））快，至少在一般情况下不会。
假设（不失一般性）m <n。 然后你的矩阵看起来像这样：
每个圆圈都是一个矩阵条目，每个箭头指示一个已知的顺序关系（箭头源的条目小于箭头目的地的条目）。
为了对矩阵进行排序，我们必须解决所有未知的顺序关系，其中一些在这里的灰色框中显示：
对所有这些框进行排序需要：
2Σk <mΩ（k log k）+（n - m + 1）Ω（m log m）
=2Ω（平方米log m）+（n - m + 1）Ω（m log m）
=Ω（mn log m）
如果元素是在k = o（mn）的特定范围内的整数，我们可以使用具有额外空间的count排序来实现O（mn），否则mnlog（min（m，n））是我们能做的最好的。
通过创建二进制搜索树，我们可以在O（mn）时间内实现这一点。 从第一列（上述示例中的元素3）中取出最后一个元素，将其作为根。 右节点将成为最后一行的n个更大的元素，左节点将成为上面元素的一个，即。 第（m-1）行或第二行的第一个元素。 同样对于这个元素，右边的节点将是该行的n个元素。 再次m-2将是左边的元素，它的行中的所有n个元素将是正确的元素。 同样向前移动，我们将在O（mn）时间创建一个二叉搜索树。 这是O（mn），因为我们在插入时没有进行搜索，它是在移动根节点指针进行遍历时的简单插入。 然后按顺序遍历这个BST，这也将是O（mn）时间。
链接地址: http://www.djcxy.com/p/22735.html上一篇: How to sort a m x n matrix which has all its m rows sorted and n columns sorted?