作者dryman (dryman)
看板CSSE
標題Re: [問題] 未排序的陣列，演算法相關問題
時間Sun May 9 23:31:35 2010
※ 引述《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)
1F：→ dryman:如果是要寫成演算法的話，也是hash key = arr val 05/09 23:41
2F：→ dryman:hash val = key 05/09 23:41
3F：→ dryman:說錯hash val = arr idx 05/09 23:42
4F：→ dryman:製作hash O(n)+O(m), 由x來尋找的話O(n) 05/09 23:43
5F：→ dryman:數組不大的話hash幾乎是O(1)真是太方便了（茶） 05/09 23:44