从按行排序的n x m数组中按升序打印数字 [英] print numbers in ascending order from an n x m array whose rows are sorted

问题描述

我们有一个n x m的矩阵，其行已排序，我们需要按升序打印数字.列不必排序.我想到的解决方案是简单地合并矩阵中的行，将它们视为单独的列表(基本上是合并排序中的合并步骤)，在合并排序中需要O(n).我想知道在这种情况下合并n个单独的数组的复杂性是什么.我以为会是O(n x m)，但我不确定.

We have an n x m matrix whose rows are sorted, we need to print the numbers in the matrix in ascending order. The columns are not necessarly sorted. The solution that came to my mind was simple merging the rows in the matrix considering them as separate lists(basically the merging step in merge sort) which in merge sort takes O(n). I wanted to know what is the complexity of merging n separate arrays as in this case. I thought it would be O(n x m) but I am not sure.

还有，一种更好的按升序打印数字的方法是什么?一次合并n个列表，还是一次合并2个列表，直到我们考虑所有行?

Also, what would be a better way to print the numbers in ascending order? merging n lists at one go or merging 2 lists at a time till we consider all rows?

谢谢！

推荐答案

What would be complexity? Its all depends how do you merge N arrays of M size!

合并的复杂程度:

• 合并两个排序的M大小的数组将按顺序进行.因此，此步骤的复杂度为O(2M).

• Merging two sorted M size array goes sequentially. So the complexity of this step is O(2M).

对于 N rows ，其中 each row is sorted 和包含M个元素.

For N rows where each row is sorted and contains Melements.

如果要这样做(线性合并):

• 首先合并两行-您将获得中间的2M size sorted array.
• 将2M array与另一个row of N size matix合并-您将得到3M size sorted array.

• Merging two rows first--you will get intermediate 2M size sorted array.
• Merge 2M array with another row of N size matix-- you will get 3M size sorted array.

以这种方式合并takes N steps和complexity would be O(N*M).

更好的方法(分治法):

• 首先合并两个连续行的所有对(1,2,3,4)，这将为您提供N/2对2M大小.在下一步中成对合并.如下所述.

• Merge all pairs of two consecutive rows first (1,2), (3,4) this give you N/2 pairs of 2M size. in next step merge pairwise. as explain below.

首先将两行和merge all N/2 pairs first and merge them配对.
例如:pair row(1,2);行(3,4); row(5,6)......您将得到= N/2 pairs each of 2M size.

First make pair of two rows and merge all N/2 pairs first and merge them.
e.g pair row(1,2); row(3,4); row(5,6) ......you will get = N/2 pairs each of 2M size.

渐进地合并所有这些中间sorted arrays util you gets a single sorted array of size N*M.这一次的复杂度将为 M * N * log(N)，总计为steps required is log(N).

Progressively Merge all this intermediate sorted arrays util you gets a single sorted array of size N*M. And this time complexity will be M*N*log(N) as total steps required is log(N).

我建议您学习合并排序及其复杂性.

这篇关于从按行排序的n x m数组中按升序打印数字的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！