推 yauhh:對,漏掉了另外一堆case.演算法還要再修正.謝謝. 05/09 16:13
※ 引述《yauhh (喲)》之銘言：
: ※ 引述《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
: : 我想請問這題大致上從哪方面下手會比較簡易
: : 謝謝
: ___Update 05/09 12:59___ 重寫個演算法
: ix_ = iy_ = 0 // Treat X[ix_] and Y[iy_] as candidate result
: if X[ix_] + Y[iy_] =\= d, do:
: ix = iy = 1 // Other records first to be considered
: while ix < length of X - 1 and iy < length of Y - 1, do:
: Check that it's ix or iy which makes d' nearer to d
: than X[ix_]+Y[iy_], where d' may be X[ix]+Y[iy_] or
: X[ix_]+Y[iy].
: If it's ix that makes d' nearer to d than ix_, ix_ = ix
: and then ix = ix+1.
: If it's iy that makes d' nearer to d than iy_, iy_ = iy
: and then iy = iy+1.
: If both ix and iy do not make any d' nearer to d,
: ix = ix+1 and iy = iy+1.
: if X[ix_] + Y[iy_] = d, result is (ix_, iy_)
: otherwise no result
我如果沒搞錯你的做法的話 下面應該是個反例:
d = 100
X = {90, 95, 96, 97, 98, 99, 60, 65}
Y = {40, 30, 50, 51, 52, 53, 54, 55}
首先 ix_ ← 0, iy_ ← 0 => X[ix_] = 90, Y[iy_] = 40 => 和 = 130
檢查 ix = 1, iy = 1 => X[ix_] + Y[iy] = 120 更好 => iy_ ← 1, 和 = 120
X[ix] + Y[iy_] = 135 iy ← 2
檢查 ix = 1, iy = 2 => X[ix_] + Y[iy] = 140 都沒有更好 => ix ← 2
X[ix] + Y[iy_] = 125 iy ← 3
以下一直到 ix = 5, iy = 6 都不會更動 ix_, iy_
檢查 ix = 6, iy = 7 => X[ix_] + Y[iy] = 145
X[ix] + Y[iy_] = 90 更好 => ix_ ← 6, 和 = 90
ix ← 7
檢查 ix = 7, iy = 7 => X[ix_] + Y[iy] = 115
X[ix] + Y[iy_] = 95 更好 => ix_ ← 7, 和 = 95
ix ← 8
迴圈終了, ix_ = 7, iy_ = 1, 因為 X[ix_] + Y[iy_] = 95 故輸出 no solution
但其實 X[6] + Y[0] = 60 + 40 = 100 ....
--
◢ ˊ_▂▃▄▂_ˋ. ◣ ▅▅ ▅▅ ι●╮ █▄▄▄▄▄
▍./◤_▂▃▄▂_◥ \'▊ ＨＡＲＵＨＩ █████ ＜■┘ ▄▄▄▄▄▄▄
▎⊿ ◤◤◥█◥◥█Δ ＩＳＭ By-gamejye ￠|\ ▌▌▌▌▌▄▌▌
▏ζ(▏●‵◥′●▊)Ψ ▏ █ ⊿Δ ▄▄▄ ▄▄▄▄
█/|▊ 〃 、 〃▋ |\ ▎ ハルヒ主義 █▄▄▄█▄▄
◥◥|◣ ‵′ ◢/'◢◢S.O.S 世界を大いに盛り上げるための涼宮ハルヒの団
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.28.92