F**********r
发帖数: 237 | 1 m*n matrix of integer, all rows and columns are sorted in ascending order.
Find the most efficient way to print out all numbers in ascending order.
偶就只能想到用个heap，显然不够优？请大侠指教！ |
e*****e
发帖数: 1275 | 2 这是young tableau 的老题阿。。。。。data structure 应该学过阿~~~
就从左角开始找好啦~~~
大雪天裸体跪求大牛找如下题名答案~~~
1. 给定M*N个不同的数，一共能生成多少个杨矩？如果允许数字有重复呢？
2. 给定杨矩，找k-th largest，复杂度多少？
【在 F**********r 的大作中提到】
: m*n matrix of integer, all rows and columns are sorted in ascending order.
: Find the most efficient way to print out all numbers in ascending order.
: 偶就只能想到用个heap，显然不够优？请大侠指教！
|
f*****w
发帖数: 2602 | |
b********n
发帖数: 29 | 4 http://stackoverflow.com/questions/4279524/how-to-sort-a-m-x-n-
在网上找到个类似的帖子。不知道他说的那个两行merge的方法他怎么算出来就是
O(m*n*log(min(m,n)))了。需要具体推一推。
我的想法是
1.找出min (m,n)，如果是行方向，就按m行多路归并，如果是列方向，就按列方向多路
归并，假设m
2.每次多路归并时候因为这多路的队头元素是拍好序的，所以不需要O(m)时间找最小值
，只需要直接提取最小值。但是提取过最小值以后，此队列下一个元素要插入到原来排
好的那一组队头中，所以要用O(lg m)时间插入(二叉查找)。
3.这样的归并要进行m*n次。
4.所以时间复杂度是O(m*n*log(min(m,n)))
PS，二楼的高手能不能仔细讲讲那个杨矩啥的是咋回事，给点reference吧 |
e*****e
发帖数: 1275 | 5 我说了阿，young tableau 从左下角开始找啊~~~比较大小决定向上还是向右走，
O(n+m)的solution阿~~~ |
c****m
发帖数: 179 | 6
你这个只是查找的？ 问题是从最小的（左上角）开始打印出sort出来的所有数。
不知道yangju对这个问题有什么快速解法？
【在 e*****e 的大作中提到】
: 我说了阿，young tableau 从左下角开始找啊~~~比较大小决定向上还是向右走，
: O(n+m)的solution阿~~~
|
e*****e
发帖数: 1275 | |
b********n
发帖数: 29 | 8 http://mathworld.wolfram.com/BumpingAlgorithm.html
我觉得他说的可能是这个。
可是和楼主问的应该不是很相关。
Bumping Algorithm是用来构造这样一个杨矩的，每插入一个新元素需要O(n+m)的时间。
楼主问的矩阵是杨矩的一个特例，可是问题在于是已经构造好的一个杨矩，要把它重新
恢复成sorted的顺序显然用O(n+m)是不可能的。O(n+m)连遍历矩阵一遍都不能完成。
我上面post的stackoverflow的帖子里的最佳回复也证明了为什么楼主的问题需要
O(n*m*log(min(m,n))) |
s*****n
发帖数: 231 | 9 一个思路,参考堆排序这个例子:
1 2 7 10 21
3 4 8 11 22
5 6 9 12 23
13 14 15 27 28
斜着看这个矩阵,每个元素的右方和下方的紧邻,都比它大,所以每三个这样的组合都是
一个堆.
1.我们提取左上角的元素,打印输出,然后将他替换成一个最大的整数,让其跟它直接向
下和向右相邻的元素比较,选择一个最小的,交换;如是类推,直到此最大数无路可降.
2.重复1,知道第(m+n)个输出. |
s*****n
发帖数: 231 | |
a********e
发帖数: 80 | 11 复杂度O(M*N)
这个矩阵就可以看成一个BST，根在右上角,左边一格是左儿子，下边一格是右儿子。左边元素比自己
小的是左子树的节点，下边元素比自己大的是右子树节点。
然后中序遍历BST就可以了。
void InOrder(int x, int y, int low, int high)
{
if ((x>=0) && (x=0) && (y
x][y]>=low))
{
InOrder(x, y-1, low, array[x][y]);
cout<
InOrder(x+1, y, array[x][y], high);
}
} |
s*****n
发帖数: 231 | 12 输入:
1 2 5
2 3 6
3 4 7
InOrder输出:
1 2 2 2 3 3 3 4 5 6 7
多了几个 |
a********e
发帖数: 80 | 13 标记一下判个重。还是O(M*N)
【在 s*****n 的大作中提到】
: 输入:
: 1 2 5
: 2 3 6
: 3 4 7
: InOrder输出:
: 1 2 2 2 3 3 3 4 5 6 7
: 多了几个
|
s*****n
发帖数: 231 | 14 输入:
1 2 5
2 7 8
3 8 9
InOrder:
1 2 2 5 7 8 8 8 9 (错误!)
BST要求所有左子树的节点都小于父节点,所有右子树节点都大于父节点,显然上面的
matrix不满足那个条件. |
