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

[dryman (dryman)]

※ 引述《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)
→ dryman:如果是要寫成演算法的話，也是hash key = arr val
→ dryman:hash val = key
→ dryman:說錯hash val = arr idx
→ dryman:製作hash O(n)+O(m), 由x來尋找的話O(n)
→ dryman:數組不大的話hash幾乎是O(1)真是太方便了（茶）