百度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)<k<(x,n) 和列(x,x)<k<(n,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算法设计题

浏览过的版块