作者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