|
|
[回复本文] 发信人: 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的算法，但是想不出来:(
|
|