How to sort a m x n matrix which has all its m rows sorted and n columns sorted?
Given a matrix with m rows and n columns, each of which are sorted. How to efficiently sort the entire matrix?
I know a solution which runs in O(mn log(min(m,n)). I am looking for a better solution.
The approach that I know basically takes 2 rows/cols at a time and applies merge operation.
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.
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]]
I don't think you can do it any faster than Ω(mn log(min(m, n)), at least not in the general case.
Suppose (without loss of generality) that m < n. Then your matrix looks like this:
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 Ω(m² log m) + (n - m + 1) Ω(m log m)
= Ω(mn log m)
如果元素是在k = o（mn）的特定范围内的整数，我们可以使用具有额外空间的count排序来实现O（mn），否则mnlog（min（m，n））是我们能做的最好的。
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.
链接地址: http://www.djcxy.com/p/22736.html上一篇: 用python下载亲爱的注释文件