※ 引述《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