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