百度HR算法设计题

wayne · 发表于 2010-6-2 14:40:29

7# litaoye 好像跟Young Tableau有一点不同~~

wayne · 发表于 2010-6-2 14:46:30

9# shshsh_0510

我在4楼给的方法，复杂度不是lgn*lgn吗

shshsh_0510 · 发表于 2010-6-2 14:48:57

I know

我是说只用中间元素做比较的方法。这样一次比较可以排除1/4矩阵中存在的可能性。如果只用此方法的话，设n*m矩阵需要的比较次数为f(n,m) 则 f(n,m) =f(n/2,m/2)+f(n/2,m) =f(n/4,m/4)+2f(n/4,m/2)+f(n/4,m) =... 且f(1,m) =f(m,1) =lg(m) 于是， f(n,n) =nlg(n)-n

qianyb · 发表于 2010-6-2 14:49:38

4# wayne 你都已经找到k了，为什么还要继续查找呢 8#的方法可以吧

wayne · 发表于 2010-6-2 14:57:47

8# qianyb k可能的范围应该是行(x,x)

shshsh_0510 · 发表于 2010-6-2 15:01:50

我是按对角线进行二分查找，找出k所在的行或列m ...

不懂

wayne · 发表于 2010-6-2 15:15:24

本帖最后由 wayne 于 2010-6-2 15:17 编辑 16# shshsh_0510 14# qianyb 我错了，应该就是如8楼所言，不过复杂度的计算好像有点问题

wayne · 发表于 2010-6-2 15:23:51

复杂度是O(n)

qianyb · 发表于 2010-6-2 15:30:10

本帖最后由 qianyb 于 2010-6-2 15:47 编辑 设n=5,矩形如下图所示，查找k=11是否在矩形(n,n)中 1 3 7 9 10 2 4 8 11 13 5 6 9 12 15 6 7 10 13 17 8 11 12 15 21 我先比较对角线上的1、4、9、13，发现11位于9（3，3）和13（4，4）之间，则11可能的地方是矩形(4,1),(n,3)和矩形（1,4),(x,n)所在的点我再在矩形(4,1),(n,3)按对角线找然后再在矩形（1,4),(x,n)按对角线找复杂度是O(n) 的

litaoye · 发表于 2010-6-2 16:06:39

http://blog.csdn.net/michealmeng ... /05/28/2489923.aspx 这是从网上搜的一篇关于杨氏矩阵的文章，配合图，还挺详细的！ 9# shshsh_0510

账号		自动登录	找回密码
密码			欢迎注册

[分享] 百度HR算法设计题