作者dryman (dryman)
看板CSSE
標題Re: [問題] 未排序的陣列，演算法相關問題
時間Mon May 10 00:43:08 2010
※ 引述《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
1F：→ dryman:突然發現原始題目是exist i,j 而不是找全部的解... 05/10 00:47
@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)
2F：→ yauhh:可是你找答案是要告知是在Y的第幾格. 05/10 00:52
3F：→ yauhh:你用yhash隨便存一個值能有什麼用呢? 05/10 00:52
4F：→ yauhh:總之,我認為你沒有找到少於O(m*n)的演算法,你只是把程式寫出 05/10 00:55
5F：→ yauhh:來而已. 05/10 00:55
6F：→ yauhh:你想想看,我在演算法觀點上寫第二段,你隨便說看不懂,那麼, 05/10 00:56
7F：→ yauhh:你隨便丟出一段perl碼,誰有必要看得懂? 05/10 00:57
8F：→ yauhh:我也可以說我把X包裝成new some(X),然後它找任何值以及由值 05/10 01:01
9F：→ yauhh:找任何index全是O(1)...但那沒意義,這是在談演算法,不是程式 05/10 01:02
10F：→ dryman:你真的懂hash是什麼嗎？... = = 05/10 01:02
11F：→ yauhh:我懂啊,但你知不知道我沒在跟你談hash 05/10 01:03
12F：→ dryman:經由hash function來確認是否有值本來就是O(1) 05/10 01:03
13F：→ yauhh:我在跟你講的是,雖然你找得到值,但沒找到對應於值的index.. 05/10 01:04
14F：→ dryman:我的key->arr val, value-> arr idx 05/10 01:04
15F：→ yauhh:可是這問題沒有解決啊,又不是你hash弄完就把答案弄出來了 05/10 01:04
16F：→ dryman:這樣就可以找到idx了啊 05/10 01:04
17F：→ dryman:push @pair, [$xhash{$item},$yhash{$num-$hash}] 05/10 01:05
18F：→ yauhh:對啊,問的就是這個啊 05/10 01:06
19F：→ dryman:這不就是用$item及$num-$item當hash key來找arr idx 05/10 01:06
20F：→ dryman:我最後面補充的，是因為原始題目是問i,j是否exists 05/10 01:07
21F：→ dryman:所以可以寫得非常短...印出exist就好 05/10 01:07
22F：→ yauhh:ok,下一個問題是,如果一個value對應到好幾個index,取這一堆 05/10 01:09
23F：→ yauhh:也是O(1)? 05/10 01:09
24F：→ dryman:噢，我的解法是假設X,Y的值都是unique 05/10 01:11
25F：→ dryman:在個別陣列中不會有重複的值，這我的確沒考慮到 05/10 01:11
26F：→ yauhh:那你不可以假設,題目並沒有假設這件事情. 05/10 01:12
27F：→ dryman:不過用hash還是可以解：利用hash做出值不重複的陣列 05/10 01:13
28F：→ dryman:同時記錄每個value的index（用hash of array） 05/10 01:13
29F：→ dryman:做出不重複的陣列後再用本解法得出arr val，用hash of arr 05/10 01:14
30F：→ dryman:反推idx 05/10 01:14
31F：→ dryman:這樣的話就是some small value * O(n) 05/10 01:15
32F：→ dryman:明早還有課，先不戰了XD 05/10 01:16
33F：→ dryman:明天再來PO改版的城市 05/10 01:16