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

[dryman (dryman)]

※ 引述《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
→ dryman:突然發現原始題目是exist i,j 而不是找全部的解...
@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)
→ yauhh:可是你找答案是要告知是在Y的第幾格.
→ yauhh:你用yhash隨便存一個值能有什麼用呢?
→ yauhh:總之,我認為你沒有找到少於O(m*n)的演算法,你只是把程式寫出
→ yauhh:來而已.
→ yauhh:你想想看,我在演算法觀點上寫第二段,你隨便說看不懂,那麼,
→ yauhh:你隨便丟出一段perl碼,誰有必要看得懂?
→ yauhh:我也可以說我把X包裝成new some(X),然後它找任何值以及由值
→ yauhh:找任何index全是O(1)...但那沒意義,這是在談演算法,不是程式
→ dryman:你真的懂hash是什麼嗎？... = =
→ yauhh:我懂啊,但你知不知道我沒在跟你談hash
→ dryman:經由hash function來確認是否有值本來就是O(1)
→ yauhh:我在跟你講的是,雖然你找得到值,但沒找到對應於值的index..
→ dryman:我的key->arr val, value-> arr idx
→ yauhh:可是這問題沒有解決啊,又不是你hash弄完就把答案弄出來了
→ dryman:這樣就可以找到idx了啊
→ dryman:push @pair, [$xhash{$item},$yhash{$num-$hash}]
→ yauhh:對啊,問的就是這個啊
→ dryman:這不就是用$item及$num-$item當hash key來找arr idx
→ dryman:我最後面補充的，是因為原始題目是問i,j是否exists
→ dryman:所以可以寫得非常短...印出exist就好
→ yauhh:ok,下一個問題是,如果一個value對應到好幾個index,取這一堆
→ yauhh:也是O(1)?
→ dryman:噢，我的解法是假設X,Y的值都是unique
→ dryman:在個別陣列中不會有重複的值，這我的確沒考慮到
→ yauhh:那你不可以假設,題目並沒有假設這件事情.
→ dryman:不過用hash還是可以解：利用hash做出值不重複的陣列
→ dryman:同時記錄每個value的index（用hash of array）
→ dryman:做出不重複的陣列後再用本解法得出arr val，用hash of arr
→ dryman:反推idx
→ dryman:這樣的話就是some small value * O(n)
→ dryman:明早還有課，先不戰了XD
→ dryman:明天再來PO改版的城市