作者mqazz1 (無法顯示)
看板CSSE
標題[問題] 未排序的陣列，演算法相關問題
時間Sat May 8 11:29:02 2010
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
我想請問這題大致上從哪方面下手會比較簡易
謝謝
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.228.27.232
1F：推 yauhh:這個問題,借一下merge sort的解法就行了. 05/09 01:56
2F：推 willhunting:merge-sort的解法願聞其詳 05/09 03:26
3F：→ yauhh:是來自於你的解的提醒(不要O(m*n)->那就O(m+n)),列在回文中. 05/09 09:57
4F：推 dryman:如果是先給Y做hash呢？ 05/09 22:12
5F：→ dryman:然後foreach X[i] ， 找Yhash中有沒有想要的值... 05/09 22:13