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

看板CSSE (電腦科學及軟體工程)作者LPH66 (-858993460)時間15年前 (2010/05/09 15:45)推噓1(1推 0噓 0→)

留言1則, 1人參與討論串5/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