weidagang2046的专栏

物格而后知致
随笔 - 8, 文章 - 409, 评论 - 101, 引用 - 0
数据加载中……

问个昨天的MSN面试题

[回复本文] 发信人: pyrope(pyrope), 信区: Algorithm
标  题: 问个昨天的MSN面试题,求教
发信站: 饮水思源 (2005年11月07日16:57:43 星期一)

有一个N*N的矩阵, 里面有N*N个数,这个矩阵的每一行,每一列都是排序好的,下面是一
个例子
1   3  7   9
2   5  13  14
6   7  25  26
20  24 30  40
现在设计一个算法,在这个矩阵中search一个数,要求尽可能快
我觉的会有lgN的算法,但是想不出来:(

--

※ 来源:·饮水思源 bbs.sjtu.edu.cn·[FROM: 59.78.35.215]

[回复本文] 发信人: keee(keee), 信区: Algorithm
标  题: Re: 问个昨天的MSN面试题,求教
发信站: 饮水思源 (2005年11月07日19:27:50 星期一)

二分不就行了
【 在 pyrope 的大作中提到: 】
: 有一个N*N的矩阵, 里面有N*N个数,这个矩阵的每一行,每一列都是排序好的,下?.
: 个例子
: 1   3  7   9
: 2   5  13  14
: 6   7  25  26
: 20  24 30  40
: 现在设计一个算法,在这个矩阵中search一个数,要求尽可能快
: 我觉的会有lgN的算法,但是想不出来:(

--

※ 来源:·饮水思源 bbs.sjtu.edu.cn·[FROM: 59.78.46.141]

[回复本文] 发信人: pyrope(pyrope), 信区: Algorithm
标  题: Re: 问个昨天的MSN面试题,求教
发信站: 饮水思源 (2005年11月07日20:14:35 星期一)

不懂怎么二分。。。能具体点么?
【 在 keee 的大作中提到: 】
: 二分不就行了
: 【 在 pyrope 的大作中提到: 】
: : 有一个N*N的矩阵, 里面有N*N个数,这个矩阵的每一行,每一列都是排序好的,?.
: : 个例子
: : 1   3  7   9
: : 2   5  13  14
: : 6   7  25  26
: : 20  24 30  40
: : 现在设计一个算法,在这个矩阵中search一个数,要求尽可能快
: : 我觉的会有lgN的算法,但是想不出来:(

--

※ 来源:·饮水思源 bbs.sjtu.edu.cn·[FROM: 59.78.35.215]

[回复本文] 发信人: keee(keee), 信区: Algorithm
标  题: Re: 问个昨天的MSN面试题,求教
发信站: 饮水思源 (2005年11月07日22:01:30 星期一)

设矩阵从(a,b)到(c,d)
取矩阵中间位置的点(x,y)与要找的数k做比较,分三种情况:相等即找到;比k小就到(a,
b)到(x,y)中找;比k大就到((x+1, b)-(c, y)), ((a, y+1)-(x, d)), ((x+1, y+1)-(c,d
))三块矩阵中找。
随便想的,欢迎拍砖
【 在 pyrope 的大作中提到: 】
: 不懂怎么二分。。。能具体点么?
: 【 在 keee 的大作中提到: 】
: : 二分不就行了

--

※ 来源:·饮水思源 bbs.sjtu.edu.cn·[FROM: 59.78.46.141]

[回复本文] 发信人: pyrope(pyrope), 信区: Algorithm
标  题: Re: 问个昨天的MSN面试题,求教
发信站: 饮水思源 (2005年11月08日10:04:03 星期二)

1   3  7   9
2   5  13  14
6   7  25  26
20  24 30  40
比k小就到(a,: b)到(x,y)中找;
这个就不对,比如我找24,然后先选到25,但是24 < 25,却不在你说的那个矩阵里
【 在 keee 的大作中提到: 】
: 设矩阵从(a,b)到(c,d)
: 取矩阵中间位置的点(x,y)与要找的数k做比较,分三种情况:相等即找到;比k小就?.
: b)到(x,y)中找;比k大就到((x+1, b)-(c, y)), ((a, y+1)-(x, d)), ((x+1, y+1)-..
: ))三块矩阵中找。
: 随便想的,欢迎拍砖
: 【 在 pyrope 的大作中提到: 】
: : 不懂怎么二分。。。能具体点么?

--

※ 来源:·饮水思源 bbs.sjtu.edu.cn·[FROM: 59.78.35.215]

[回复本文] 发信人: SYSADMIN(此人已死,有事烧纸--挂站中), 信区: Algorithm
标  题: Re: 问个昨天的MSN面试题,求教
发信站: 饮水思源 (2005年11月08日10:05:52 星期二), 转信

2分法,

【 在 pyrope (pyrope) 的大作中提到: 】
: 有一个N*N的矩阵, 里面有N*N个数,这个矩阵的每一行,每一列都是排序好的,下面是一
: 个例子
: 1   3  7   9
: 2   5  13  14
: 6   7  25  26
: 20  24 30  40
: 现在设计一个算法,在这个矩阵中search一个数,要求尽可能快
: 我觉的会有lgN的算法,但是想不出来:(
--

※ 来源:·饮水思源 bbs.sjtu.edu.cn·[FROM: 202.120.61.133]

[回复本文] 发信人: keee(keee), 信区: Algorithm
标  题: Re: 问个昨天的MSN面试题,求教
发信站: 饮水思源 (2005年11月08日12:37:40 星期二), 转信

疏忽了。。。。
那就再多找两个矩阵好了,无所谓的
反正每次都能去掉1/4的元素,阶是log(n*n)的

【 在 pyrope (pyrope) 的大作中提到: 】
: 1   3  7   9
: 2   5  13  14
: 6   7  25  26
: 20  24 30  40
: 比k小就到(a,: b)到(x,y)中找;
: 这个就不对,比如我找24,然后先选到25,但是24 < 25,却不在你说的那个矩阵里
: 【 在 keee 的大作中提到: 】
: : 设矩阵从(a,b)到(c,d)
: : 取矩阵中间位置的点(x,y)与要找的数k做比较,分三种情况:相等即找到;比k小就?.
: : b)到(x,y)中找;比k大就到((x+1, b)-(c, y)), ((a, y+1)-(x, d)), ((x+1, y+1)-..
: .................(以下省略)
--

※ 来源:·饮水思源 bbs.sjtu.edu.cn·[FROM: 59.78.46.141]

[回复本文] 发信人: Comars(New season comes), 信区: Algorithm
标  题: Re: 问个昨天的MSN面试题,求教
发信站: 饮水思源 (2005年11月08日12:44:25 星期二), 转信

按照
T(n) = 3T(n/2) 计算,阶是 O(n^(log3)) 大概是 O(n^1.58)
不是 log(n*n)

【 在 keee (keee) 的大作中提到: 】
: 疏忽了。。。。
: 那就再多找两个矩阵好了,无所谓的
: 反正每次都能去掉1/4的元素,阶是log(n*n)的
: 【 在 pyrope (pyrope) 的大作中提到: 】
: : 1   3  7   9
: : 2   5  13  14
: : 6   7  25  26
: : 20  24 30  40
: : 比k小就到(a,: b)到(x,y)中找;
: : 这个就不对,比如我找24,然后先选到25,但是24 < 25,却不在你说的那个矩阵里
: .................(以下省略)

--
  从前有座山
  山上有个庙
  庙里有俩和尚……


※ 修改:·Comars 于 11月08日12:44:37 修改本文·[FROM: 202.120.61.1]
※ 来源:·饮水思源 bbs.sjtu.edu.cn·[FROM: 202.120.61.1]

[回复本文] 发信人: keee(keee), 信区: Algorithm
标  题: Re: 问个昨天的MSN面试题,求教
发信站: 饮水思源 (2005年11月08日12:56:51 星期二), 转信

汗。。。
胡说八道被抓了。。
【 在 Comars (New season comes) 的大作中提到: 】
: 按照
: T(n) = 3T(n/2) 计算,阶是 O(n^(log3)) 大概是 O(n^1.58)
: 不是 log(n*n)
: 【 在 keee (keee) 的大作中提到: 】
: : 疏忽了。。。。
: : 那就再多找两个矩阵好了,无所谓的
: : 反正每次都能去掉1/4的元素,阶是log(n*n)的
: : .................(以下省略)
--

※ 来源:·饮水思源 bbs.sjtu.edu.cn·[FROM: 59.78.46.141]

[回复本文] 发信人: keee(keee), 信区: Algorithm
标  题: Re: 问个昨天的MSN面试题,求教
发信站: 饮水思源 (2005年11月08日12:58:29 星期二), 转信

有更好的算法吗
【 在 keee (keee) 的大作中提到: 】
: 汗。。。
: 胡说八道被抓了。。
: 【 在 Comars (New season comes) 的大作中提到: 】
: : 按照
: : T(n) = 3T(n/2) 计算,阶是 O(n^(log3)) 大概是 O(n^1.58)
: : 不是 log(n*n)
--

※ 来源:·饮水思源 bbs.sjtu.edu.cn·[FROM: 59.78.46.141]

[回复本文] 发信人: pyrope(pyrope), 信区: Algorithm
标  题: Re: 问个昨天的MSN面试题,求教
发信站: 饮水思源 (2005年11月08日13:50:57 星期二)

按你那样的算法的话,是多项式复杂度,还不如直接找是nlgn,
那个HR说好像是有lgn复杂度的算法的,我觉的也应该是有的
【 在 keee 的大作中提到: 】
: 有更好的算法吗
: 【 在 keee (keee) 的大作中提到: 】
: : 汗。。。
: : 胡说八道被抓了。。

--

※ 来源:·饮水思源 bbs.sjtu.edu.cn·[FROM: 59.78.35.215]

[回复本文] 发信人: paradisor(paradisor), 信区: Algorithm
标  题: Re: 问个昨天的MSN面试题,求教
发信站: 饮水思源 (2005年11月08日15:55:47 星期二)

hehe
【 在 keee 的大作中提到: 】
: 汗。。。
: 胡说八道被抓了。。
: 【 在 Comars (New season comes) 的大作中提到: 】
: : 按照
: : T(n) = 3T(n/2) 计算,阶是 O(n^(log3)) 大概是 O(n^1.58)
: : 不是 log(n*n)

--
羽箭雕弓,忆呼鹰古垒,截虎平川。 吹笳暮归野帐,雪压青毡。
淋漓醉墨,看龙蛇飞落蛮笺。 人误许,诗情将略,一时才气超然。

何事又作南来,看重阳药市,元夕灯山。 花时万人乐处,攲帽垂鞭。
闻歌感旧,尚时时流涕尊前。 君记取:封侯事在,功名不信由天。


※ 来源:·饮水思源 bbs.sjtu.edu.cn·[FROM: 59.78.46.143]

[回复本文] 发信人: kerrigan(用户昵称), 信区: Algorithm
标  题: Re: 问个昨天的MSN面试题,求教
发信站: 饮水思源 (2005年11月08日16:56:35 星期二)

我可以提供一个log(n)+log(n-1)+..+log(1) = log(n!)的算法
举例来说,假设要找8
现在第一行中2分查找(logn),确定位置在7,9之间
7左上的元素小于7,9右上的元素大于9,删除这些元素
那么可以确定8在
2   5  13 
6   7  25  
20  24 30  
即T(n)=T(n-1)+logn -> T(n)=log(n!)
【 在 pyrope 的大作中提到: 】
: 有一个N*N的矩阵, 里面有N*N个数,这个矩阵的每一行,每一列都是排序好的,下?.
: 个例子
: 1   3  7   9
: 2   5  13  14
: 6   7  25  26
: 20  24 30  40
: 现在设计一个算法,在这个矩阵中search一个数,要求尽可能快
: 我觉的会有lgN的算法,但是想不出来:(

posted on 2005-11-08 22:08 weidagang2046 阅读(662) 评论(2)  编辑  收藏 所属分类: Others

评论

# re: 问个昨天的MSN面试题  回复  更多评论   

a[n][n]为矩阵,查找x

for(i=0,j=n-1;i<n && j>=0 && a[i][j]!=x;i+=a[i][j]<x,j-=a[i][j]>x);
2005-11-11 23:12 | weidagang2046

# re: 问个昨天的MSN面试题  回复  更多评论   

楼上正解。牛人。时间复杂度O(n)。空间复杂度O(1)。缺点:代码不宜读,没有考虑找不到的情况。@weidagang2046

2011-09-09 17:23 | liang

只有注册用户登录后才能发表评论。


网站导航: