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

[dryman (dryman)]

# form y hash of array
# key -> value of y array
# value -> array of y indexes which point to the associative value

$idx = 0;
for $item (@y) {
    push @{ $y_hash_of_arr{$item} }, $idx++;      # push $idx into
}                                                 # y_hash_of_arr


$idx = 0;
for $item (@x) {
    push @{ $inter_of_x{$item} }, $idx if exists $y_hash_of_arr{$num-$item};
    $idx++;
}

@i = values %inter_of_x;

for $item (keys %inter_of_x){
    push @yvalues, $num-$item;
}
@j = @y_hash_of_arr{@yvalues};

# inter_of_x 是只找出 x array 中符合 $num-$item 的雜湊
# 其鍵為 $item  （就是 x array 的 value）
# 其值為 array of idx ，使用陣列是因為可能有多個idx含有同個值
#
# 根據inter_of_x可得到符合要求的yvalue
# 再由yvalue找到arr of idx of y


===============================

原始題目只要exists就好
@Hoy(@y)=();    # 只要鍵不用值
for (@x) { print "exists" and last if exists $Hoy{$num-$_}; }

這樣的話只會印出 "exists" 一次就會跳出迴圈了XD

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 220.136.177.207
→ dryman:BTW hash值重複時，舊的值會被覆蓋掉，但若是單純判斷有無
→ dryman:就沒關係
→ dryman:
→ dryman:抓出多個idx的版本很醜..不知道Perl有沒有比較好的idx func
→ yauhh:你這樣題意也改掉了,輸入資料的內容也改掉了,談Big-O沒意義
→ yauhh:你知道什麼是Big-O嗎? Big-O是指普遍的情況下,你的程式需要
→ yauhh:執行的步驟數目與輸入的資料量有什麼關連.
→ yauhh:如果要先假設輸入是什麼,那我也可以假設X,Y陣列全都是1,
→ yauhh:這樣演算法多簡單啊,還全都O(1)呢!
→ yauhh:可是這樣玩沒有意義.
→ yauhh:而你抓著perl語法自high,在演算法方面有什麼意義?
→ dryman:哪裡要假設輸入資料是什麼請你說清楚
※ 編輯: dryman          來自: 140.112.46.31        (05/10 13:28)
→ dryman:演算法之前有推過，這裡再提一次：由yhash找出Y當中符合
→ dryman:資格的值，製作yhash及跑過整個x的big-O個別為O(m),O(n)
→ dryman:hash的key是arr val, 值的話在本篇是多個idx的集合
→ dryman:但存取值因為是O(1)，判斷key是否存在也是O(1)
→ dryman:故整體的big-O只有O(m)+O(n)
→ dryman:
→ dryman:之前寫的演算法無法輸出重複的idx，但這不是題目要求的
→ dryman:因為題目只有說要找是否存在ij
推 ledia:yauhh 每次都搞不清楚狀況... 不意外, 你的做法很好了
→ ledia:拿空間換時間, 算是一種很有效加速
→ ledia:不過有的 hash 的 implementation 不見得是 O(1)
→ ledia:不過概念到就是了
→ dryman:是沒錯啦XD 製作時和存取都不一定是O(1)
→ yauhh:沒有搞不清楚喔.而是旁觀者ledia你沒看清楚我在問什麼.
→ yauhh:dryman你說,喔,如果陣列每個值都unique就ok,全都是O(n)搞定
→ yauhh:但是資料怎麼會乖乖去unique給你容易O(n)? 相對的,談演算法
→ yauhh:的人所遵守的遊戲規則是,輸入是什麼,要原封不動. 題目說
→ yauhh:unsorted list,不知道有沒有排序,那你給他定一個值unique有
→ yauhh:何意義?
→ yauhh:所以我說,喔,你要把值自己取unique一段說演算法會變成O(n),
→ yauhh:那我也可以取兩陣列值只存在一種值對應另一種值的情況,然後
→ yauhh:說演算法可以O(1). 這兩種都是沒有意義,但是可以幫助自己
→ yauhh:自high的.
→ yauhh:你說的都有道理,但只是在特定情況之下有道理而已.
→ yauhh:如果要談值有重覆的,你敢不敢說你的辦法仍保持在O(n)?
→ yauhh:當題目說出(i,j)的字眼時,你覺得你回答一個"yes"或"no"會
→ yauhh:得幾分?
→ yauhh:你只限定自己演算法找到就回答"yes",可是別人在找演算法來用
→ yauhh:時,翻到你的演算法就會有個感覺:效果是不錯,但是答非所問,
→ yauhh:實際用途不會這樣做.
→ yauhh:怎麼樣,半路殺出來嗆聲的ledia,你說說看我到底哪裡沒搞清楚?
→ yauhh:還有,你一跳出來就只會說,因為是*我*搞不清楚,所以沒錯...
→ yauhh:這不就叫做人身攻擊嗎? 長久以來你並沒有進步呢.
推 Huangs:我不懂強者 yauhh 在質疑什麼  dryman的方法
→ Huangs:無論輸入是否unique都可以運作啊  哪裡答非所問了？
※ 編輯: dryman          來自: 140.112.46.31        (05/18 22:10)