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