PTT數位生活區 / CSSE (電腦科學及軟體工程)

Re: [問題] 未排序的陣列，演算法相關問題

看板CSSE (電腦科學及軟體工程)作者 (dryman)時間14年前 (2010/05/10 00:43), 編輯推噓0(0推 0噓 33→)
留言33則, 2人參與, 最新討論串9/13 (看更多)
※ 引述《yauhh (喲)》之銘言： : ※ 引述《dryman (dryman)》之銘言： : : 用Perl隨便兜一個 : : 雖然這不能當演算法的解答啦 : : 不過就應用上還蠻不錯的XD : : @x = 1..60; : : @y = 30..100; : : $num = 50; : : @xhash{@x}=0..$#x; : : @yhash{@y}=0..$#y; : : foreach $item (@x) { : : push @pair,[$xhash{$item},$yhash{$num-$item}] if exists $yhash{$num-$item}; : : } : 看你這一段程式有些小小疑惑,就當做hash真強到找什麼都O(1)好了, : 先考慮一種情況: : 首先把X,Y陣列的值都丟到xhash和yhash, : 你找到一個$xhash{$item},$item表示X陣列的一格值,所以用$num-$item找yhash, 這行看不懂 我是對@x做迴圈 foreach $item (@x) 可讀作 for each $item in @x array : 找到Y陣列中的另一格值$yhash{$num-$item}. : 接下來有個問題是:$yhash{$num-$item}是Y的第幾格? hash 中沒有格不格的問題啊@ @ $yhash{$num-$item} 是把$num-$item的值 丟進" if exists $yhash " 中 （這句不適合拆開來讀，因為$yhash在前面有exists時是回傳布林值 沒有exists 時則是回傳此鍵對應的值） 這一步的動作為O(1) : 在這個情況中,看起來沒有處理這個... 而是否沒處理這個讓你得到O(n)的印象? : 考慮另一種情況: : 也許我不懂perl,把它看錯了,其實是把X,Y陣列的每一格,包含{index,value}都丟進 : hash. 所以$xhash{$item}是{i,v}這樣的內容,把它拿去yhash找的時候, : 一定要做兩個動作: : 1. 把v取出找$num-v : 2. 在yhash找到合適的{j,$num-v}. : 然後你才可以找到一對(i,j),其X[i]與Y[j]總和為$num. : 在這種情況中,找到對應的{j,$num-v}顯然不會是O(1)的,假設有k個這種j, : 就要找j次. 這樣算總數起碼也是個O(m*k),m是X長度,k可視同為Y長度. : 是哪種情況呢? 我想您可能是看錯foreach $item (@x) 這一行吧XD 後面這裡的解釋我都看不太懂:P -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 220.136.185.230
→
05/10 00:47, , 1F
突然發現原始題目是exist i,j 而不是找全部的解...
05/10 00:47, 1F
@yhash{@y} = 0..$#y; for $item (@x){ print "exist\n" if exists $yhash{$num-$item}; } XDDDDD 超級有"語感"的!! Perl是語言學家開發出來的程式語言用起來真的抄酷！ ※ 編輯: dryman 來自: 220.136.185.230 (05/10 00:49)
→
05/10 00:52, , 2F
可是你找答案是要告知是在Y的第幾格.
05/10 00:52, 2F
→
05/10 00:52, , 3F
你用yhash隨便存一個值能有什麼用呢?
05/10 00:52, 3F
→
05/10 00:55, , 4F
總之,我認為你沒有找到少於O(m*n)的演算法,你只是把程式寫出
05/10 00:55, 4F
→
05/10 00:55, , 5F
來而已.
05/10 00:55, 5F
→
05/10 00:56, , 6F
你想想看,我在演算法觀點上寫第二段,你隨便說看不懂,那麼,
05/10 00:56, 6F
→
05/10 00:57, , 7F
你隨便丟出一段perl碼,誰有必要看得懂?
05/10 00:57, 7F
→
05/10 01:01, , 8F
我也可以說我把X包裝成new some(X),然後它找任何值以及由值
05/10 01:01, 8F
→
05/10 01:02, , 9F
找任何index全是O(1)...但那沒意義,這是在談演算法,不是程式
05/10 01:02, 9F
→
05/10 01:02, , 10F
你真的懂hash是什麼嗎？... = =
05/10 01:02, 10F
→
05/10 01:03, , 11F
我懂啊,但你知不知道我沒在跟你談hash
05/10 01:03, 11F
→
05/10 01:03, , 12F
經由hash function來確認是否有值本來就是O(1)
05/10 01:03, 12F
→
05/10 01:04, , 13F
我在跟你講的是,雖然你找得到值,但沒找到對應於值的index..
05/10 01:04, 13F
→
05/10 01:04, , 14F
我的key->arr val, value-> arr idx
05/10 01:04, 14F
→
05/10 01:04, , 15F
可是這問題沒有解決啊,又不是你hash弄完就把答案弄出來了
05/10 01:04, 15F
→
05/10 01:04, , 16F
這樣就可以找到idx了啊
05/10 01:04, 16F
→
05/10 01:05, , 17F
push @pair, [$xhash{$item},$yhash{$num-$hash}]
05/10 01:05, 17F
→
05/10 01:06, , 18F
對啊,問的就是這個啊
05/10 01:06, 18F
→
05/10 01:06, , 19F
這不就是用$item及$num-$item當hash key來找arr idx
05/10 01:06, 19F
→
05/10 01:07, , 20F
我最後面補充的，是因為原始題目是問i,j是否exists
05/10 01:07, 20F
→
05/10 01:07, , 21F
所以可以寫得非常短...印出exist就好
05/10 01:07, 21F
→
05/10 01:09, , 22F
ok,下一個問題是,如果一個value對應到好幾個index,取這一堆
05/10 01:09, 22F
→
05/10 01:09, , 23F
也是O(1)?
05/10 01:09, 23F
→
05/10 01:11, , 24F
噢，我的解法是假設X,Y的值都是unique
05/10 01:11, 24F
→
05/10 01:11, , 25F
在個別陣列中不會有重複的值，這我的確沒考慮到
05/10 01:11, 25F
→
05/10 01:12, , 26F
那你不可以假設,題目並沒有假設這件事情.
05/10 01:12, 26F
→
05/10 01:13, , 27F
不過用hash還是可以解：利用hash做出值不重複的陣列
05/10 01:13, 27F
→
05/10 01:13, , 28F
同時記錄每個value的index（用hash of array）
05/10 01:13, 28F
→
05/10 01:14, , 29F
做出不重複的陣列後再用本解法得出arr val，用hash of arr
05/10 01:14, 29F
→
05/10 01:14, , 30F
反推idx
05/10 01:14, 30F
→
05/10 01:15, , 31F
這樣的話就是some small value * O(n)
05/10 01:15, 31F
→
05/10 01:16, , 32F
明早還有課，先不戰了XD
05/10 01:16, 32F
→
05/10 01:16, , 33F
明天再來PO改版的城市
05/10 01:16, 33F
‣ 更多 dryman 的文章
文章代碼(AID): #1BvkOU3H (CSSE)
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 9 之 13 篇)：
排序： 最舊先 | 最新先 | 留言數
在新視窗開啟完整討論串 (共13篇)
CSSE 近期熱門文章
更多 近期熱門文章 >>
PTT數位生活區 即時熱門文章
更多 即時熱門文章 >>
‣ 更多 dryman 的文章
文章代碼(AID): #1BvkOU3H (CSSE)