Given a matrix with m rows and n columns, each of which are sorted. How to efficiently sort the entire matrix?
给定一个m行和n列的矩阵，每个列都是有序的。如何有效地对整个矩阵进行排序?
I know a solution which runs in O(m n log(min(m,n)). I am looking for a better solution.
我知道一个在O(m n log(min(m,n))中运行的解。我正在寻找一个更好的解决方案。
The approach that I know basically takes 2 rows/cols at a time and applies merge operation.
我所知道的方法基本上每次只需要2行/cols，并应用合并操作。
Here is an example:
这是一个例子:
[[1,4,7,10],
[2,5,8,11],
[3,6,9,12]]
is the input martix which has every row and column sorted.
是已排序的每一行和列的输入martix。
Expected output is:
预期的输出是:
[1,2,3,4,5,6,7,8,9,10,11,12]
Another example:
另一个例子:
[[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]]
3 个解决方案
#1
46
I don't think you can do it any faster than Ω(m n log(min(m, n)), at least not in the general case.
我不认为你能做得比(m n log(min(m, n))快，至少在一般情况下是这样。
Suppose (without loss of generality) that m < n. Then your matrix looks like this:
假设(不失一般性)m < n，那么你的矩阵是这样的:
Each circle is a matrix entry and each arrow indicates a known order relation (the entry at the source of the arrow is smaller than the entry at the destination of the arrow).
每个圆都是一个矩阵条目，每个箭头表示一个已知的顺序关系(箭头的源处的条目比箭头目的地的条目要小)。
To sort the matrix, we must resolve all the unknown order relations, some of which are shown in the grey boxes here:
为了对矩阵进行排序，我们必须解决所有未知的顺序关系，其中一些是在灰色方框中显示的:
Sorting all of these boxes takes:
对所有这些盒子进行分类:
2 Σk < m Ω(k log k) + (n - m + 1) Ω(m log m)
2 k < m (k log k) + (n - m + 1) (m log m)
= 2 Ω(m² log m) + (n - m + 1) Ω(m log m)
= 2 (m log m) + (n - m + 1) (m log m)
= Ω(m n log m)
=Ω(m n log m)
#2
0
If elements are integers within a certain range k where K=o(mn), we can use count sort with extra space to achieve O(mn), otherwise the mnlog(min(m,n)) is the best we can do.
如果元素在k =o(mn)的某个范围k中是整数，那么我们可以使用计数排序来获得额外的空间来实现o(mn)，否则mnlog(min(m,n))是我们能做的最好的。
#3
0
By creating a Binary Search Tree, we can achieve this in O(mn) time. Take the last element from the first column (element 3 in the example mentioned above), make it as a root. Right nodes will be the n greater elements of that last row and left node will be the one above element ie. the (m-1)th or the 1st element from the second last row. Similarly for this element, the right nodes will be the n elements of that row. Again m-2 will be the left element and all the n elements in it's row will be the right elements. Similarly moving forward we'll have a binary search tree created in O(mn) time. This is O(mn) because we are not searching while inserting, it's a simple insert while traversing by shifting the root node pointer. Then inorder traversal of this BST will be done which will also be O(mn) time.
通过创建一个二叉搜索树，我们可以在O(mn)时间内实现这个目标。从第一列(上面提到的例子中的元素3)中提取最后一个元素，将其作为根。右节点将是最后一行的n个较大的元素，而左节点将是上面的一个元素。(m-1)th或第2行中的第1个元素。类似地，对于这个元素，右节点将是该行的n个元素。m-2将会是左边的元素所有的n元素都是正确的元素。同样，我们将在O(mn)中创建一个二叉搜索树。这是O(mn)，因为我们在插入时没有搜索，它是一个简单的插入，通过移动根节点指针来遍历。然后，这个BST的内序遍历将被完成，这也将是O(mn)时间。
#1
46
I don't think you can do it any faster than Ω(m n log(min(m, n)), at least not in the general case.
我不认为你能做得比(m n log(min(m, n))快，至少在一般情况下是这样。
Suppose (without loss of generality) that m < n. Then your matrix looks like this:
假设(不失一般性)m < n，那么你的矩阵是这样的:
Each circle is a matrix entry and each arrow indicates a known order relation (the entry at the source of the arrow is smaller than the entry at the destination of the arrow).
每个圆都是一个矩阵条目，每个箭头表示一个已知的顺序关系(箭头的源处的条目比箭头目的地的条目要小)。
To sort the matrix, we must resolve all the unknown order relations, some of which are shown in the grey boxes here:
为了对矩阵进行排序，我们必须解决所有未知的顺序关系，其中一些是在灰色方框中显示的:
Sorting all of these boxes takes:
对所有这些盒子进行分类:
2 Σk < m Ω(k log k) + (n - m + 1) Ω(m log m)
2 k < m (k log k) + (n - m + 1) (m log m)
= 2 Ω(m² log m) + (n - m + 1) Ω(m log m)
= 2 (m log m) + (n - m + 1) (m log m)
= Ω(m n log m)
=Ω(m n log m)
#2
0
If elements are integers within a certain range k where K=o(mn), we can use count sort with extra space to achieve O(mn), otherwise the mnlog(min(m,n)) is the best we can do.
如果元素在k =o(mn)的某个范围k中是整数，那么我们可以使用计数排序来获得额外的空间来实现o(mn)，否则mnlog(min(m,n))是我们能做的最好的。
#3
0
By creating a Binary Search Tree, we can achieve this in O(mn) time. Take the last element from the first column (element 3 in the example mentioned above), make it as a root. Right nodes will be the n greater elements of that last row and left node will be the one above element ie. the (m-1)th or the 1st element from the second last row. Similarly for this element, the right nodes will be the n elements of that row. Again m-2 will be the left element and all the n elements in it's row will be the right elements. Similarly moving forward we'll have a binary search tree created in O(mn) time. This is O(mn) because we are not searching while inserting, it's a simple insert while traversing by shifting the root node pointer. Then inorder traversal of this BST will be done which will also be O(mn) time.
通过创建一个二叉搜索树，我们可以在O(mn)时间内实现这个目标。从第一列(上面提到的例子中的元素3)中提取最后一个元素，将其作为根。右节点将是最后一行的n个较大的元素，而左节点将是上面的一个元素。(m-1)th或第2行中的第1个元素。类似地，对于这个元素，右节点将是该行的n个元素。m-2将会是左边的元素所有的n元素都是正确的元素。同样，我们将在O(mn)中创建一个二叉搜索树。这是O(mn)，因为我们在插入时没有搜索，它是一个简单的插入，通过移动根节点指针来遍历。然后，这个BST的内序遍历将被完成，这也将是O(mn)时间。