买二手房弱问 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Living

买二手房弱问

买二手房弱问# Living

F*r2010-10-17 07:10

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，显然不够优？请大侠指教！

b*m2010-10-17 07:10

2 楼

谢谢了，菜鸟问题

b*r2010-10-17 07:10

3 楼

看上一个房子，厨房没有pre－vent，要是想自己装一个，会不会很麻烦？还是要请人
做？这个会不会涉及到structure？
另一个若问题。如果住了以后发现有什么东西坏了（假如说furance),是不是要自己找人
修呀？前方主会不会有什么warranty可以transfer给我？
多谢回答！

e*e2010-10-17 07:10

4 楼

这是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，显然不够优？请大侠指教！

d*n2010-10-17 07:10

5 楼

J1也可以申请EB1b，先递140，然后申请J1waiver，然后递485.

【在 b******m 的大作中提到】

: 谢谢了，菜鸟问题

l*o2010-10-17 07:10

6 楼

关于第二个问题，好像有的卖家可以提供warranty的，就是买个保险。

找人

【在 b***r 的大作中提到】

: 看上一个房子，厨房没有pre－vent，要是想自己装一个，会不会很麻烦？还是要请人
: 做？这个会不会涉及到structure？
: 另一个若问题。如果住了以后发现有什么东西坏了（假如说furance),是不是要自己找人
: 修呀？前方主会不会有什么warranty可以transfer给我？
: 多谢回答！

f*w2010-10-17 07:10

7 楼

我对这题也有疑问同等高手

l*i2010-10-17 07:10

8 楼

How about OPT?

b*r2010-10-17 07:10

9 楼

多谢！

【在 l*****o 的大作中提到】

: 关于第二个问题，好像有的卖家可以提供warranty的，就是买个保险。
:
: 找人

b*n2010-10-17 07:10

10 楼

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行多路归并，如果是列方向，就按列方向多路
归并，假设m2.每次多路归并时候因为这多路的队头元素是拍好序的，所以不需要O(m)时间找最小值
，只需要直接提取最小值。但是提取过最小值以后，此队列下一个元素要插入到原来排
好的那一组队头中，所以要用O(lg m)时间插入(二叉查找)。
3.这样的归并要进行m*n次。
4.所以时间复杂度是O(m*n*log(min(m,n)))
PS，二楼的高手能不能仔细讲讲那个杨矩啥的是咋回事，给点reference吧

o*s2010-10-17 07:10

11 楼

right
申请eb1a需要有h1a

【在 b******m 的大作中提到】

: 谢谢了，菜鸟问题

s*i2010-10-17 07:10

12 楼

vent out可以自己找人弄，either从侧墙或者从屋顶，你自己研究一下怎么走管子
比较方便。

e*e2010-10-17 07:10

13 楼

我说了阿，young tableau 从左下角开始找啊~~~比较大小决定向上还是向右走，
O(n+m)的solution阿~~~

c*m2010-10-17 07:10

14 楼

你这个只是查找的？问题是从最小的（左上角）开始打印出sort出来的所有数。
不知道yangju对这个问题有什么快速解法？

【在 e*****e 的大作中提到】

: 我说了阿，young tableau 从左下角开始找啊~~~比较大小决定向上还是向右走，
: O(n+m)的solution阿~~~

e*e2010-10-17 07:10

15 楼

阿~~~看错题目了~~~
汗~~~~

b*n2010-10-17 07:10

16 楼

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*n2010-10-17 07:10

17 楼

一个思路,参考堆排序这个例子:
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*n2010-10-17 07:10

18 楼

复杂度 mnlog(max(m,n)).

a*e2010-10-17 07:10

19 楼

复杂度O(M*N)
这个矩阵就可以看成一个BST，根在右上角,左边一格是左儿子，下边一格是右儿子。左边元素比自己
小的是左子树的节点，下边元素比自己大的是右子树节点。
然后中序遍历BST就可以了。
void InOrder(int x, int y, int low, int high)
{
if ((x>=0) && (x=0) && (yx][y]>=low))
{
InOrder(x, y-1, low, array[x][y]);
cout<InOrder(x+1, y, array[x][y], high);
}
}

s*n2010-10-17 07:10

20 楼

输入:
1 2 5
2 3 6
3 4 7
InOrder输出:
1 2 2 2 3 3 3 4 5 6 7
多了几个

a*e2010-10-17 07:10

21 楼

标记一下判个重。还是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*n2010-10-17 07:10

22 楼

输入:
1 2 5
2 7 8
3 8 9
InOrder:
1 2 2 5 7 8 8 8 9 (错误!)
BST要求所有左子树的节点都小于父节点,所有右子树节点都大于父节点,显然上面的
matrix不满足那个条件.