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

看板CSSE作者 (-858993460)時間14年前 (2010/05/09 15:45), 編輯推噓1(100)
留言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 .... -- ˊ_▂▃▄▂_ˋ. ◣          ▅▅ ▅▅ ι●╮   ./◤_▂▃▄▂_◥ \'▊   HARUHI █████ <■┘   ◤◤◥█◥◥█Δ   ISM    By-gamejye ¢|\   ▌▌ζ(▏●‵◥′●)Ψ ▏           █    ⊿Δ    /|▋ |\ ▎         ハルヒ主義      ▄█ ◥◥|◣ ‵′ ◢/'◢◢S.O.S 世界をいに盛り上げるための宮ハルヒの    -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.112.28.92

05/09 16:13, , 1F
對,漏掉了另外一堆case.演算法還要再修正.謝謝.
05/09 16:13, 1F
文章代碼(AID): #1BvcW37R (CSSE)
討論串 (同標題文章)
以下文章回應了本文
完整討論串 (本文為第 5 之 13 篇):
文章代碼(AID): #1BvcW37R (CSSE)