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

7# litaoye

好像跟Young Tableau有一点不同~~

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

9# shshsh_0510

:victory:
我在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)中
13   7 910
24   8 11 13
56   9 12 15
6710 13 17
811 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/michealmeng555/archive/2008/05/28/2489923.aspx

这是从网上搜的一篇关于杨氏矩阵的文章，配合图，还挺详细的！

9# shshsh_0510
页: 1 [2] 3
查看完整版本: 百度HR算法设计题