如何排序所有m行排序和n列排序的m x n矩阵？ [英] How to sort a m x n matrix which has all its m rows sorted and n columns sorted?

问题描述

给定一个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]] 
  

解决方案

我不认为你可以做得比Ω更快（ mn log（min（ m ， n ））），至少不在一般情况。

假设（不失一般性） m < n 。那么你的矩阵如下所示：

每个圆是一个矩阵条目，每个箭头表示一个已知的顺序关系（箭头来源的条目小于

为了排序矩阵，我们必须解决所有未知的顺序关系，其中一些在灰色框中显示：

排序所有这些框需要：

2Σ _{>< > + 1）Ω（ m log m ）}

= 2Ω（ >²²²m）））））>>>>>>>>>>>>>>>>>>>>>>>>>>>>> <> <<<<<<<<<<<）

=Ω（ mn log m ）

< blockquote>

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(m n 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 Ω(m n 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)

= Ω(m n log m)

这篇关于如何排序所有m行排序和n列排序的m x n矩阵？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！