Re: [問題] 未排序的陣列，演算法相關問題
※ 引述《mqazz1 (無法顯示)》之銘言：
: given two unsorted arrays X and Y,
: each contains m and n numbers, separately.
: design an algorithm so that,
: given a number d,
: it could determine if there exists two integers i and j,
: such that X[i] + Y[i] = d
: use less than O(m*n) running time
: 我想請問這題大致上從哪方面下手會比較簡易
: 謝謝
用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};
}
語法解釋如下：
# 假設x=1~60, y=30~100, d=50; 這部份可以隨便改
# 要處理是否重複太麻煩了...
@x = 1..60;
@y = 30..100;
$num = 50;
# 雜湊鍵為陣列值，雜湊值為陣列索引
@xhash{@x}=0..$#x;
@yhash{@y}=0..$#y;
# 這三行其實就已經把問題解完了XDDD
foreach $item (@x) {
push @pair,[$xhash{$item},$yhash{$num-$item}] if exists $yhash{$num-$item};
}
這邊語法比較複雜
@pair是一個array of array
比較好懂的版本是寫
if (exists $yhash{$num-$item}){
push @xidx, $xhash{$item};
push @yidx, $yhash{$item};
}
# 印出
foreach $item (@pair) { print
$item->[0] ." "
.$x[$item->[0]]." "
.$item->[1]." "
.$y[$item->[1]] ."\n" };
使用arr of arr 似乎不會讓印出工作變得比較簡單 ~"~
唯一比較長比較醜的地方...
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.46.31
※ 編輯: dryman 來自: 140.112.46.31 (05/09 23:34)
→
05/09 23:41, , 1F
05/09 23:41, 1F
→
05/09 23:41, , 2F
05/09 23:41, 2F
→
05/09 23:42, , 3F
05/09 23:42, 3F
→
05/09 23:43, , 4F
05/09 23:43, 4F
→
05/09 23:44, , 5F
05/09 23:44, 5F
討論串 (同標題文章)