作者Hatred (yo)
看板CSSE
标题Re: [问题] 未排序的阵列，演算法相关问题
时间Sat May 8 12:23:29 2010
※ 引述《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
这里是 X[i] + Y[j] = d 吧? 不然 j 会没有用到...
: use less than O(m*n) running time
: 我想请问这题大致上从哪方面下手会比较简易
: 谢谢
或许可以这样做:
不妨假设 m<=n, 我们先把 d-X[1], ..., d-X[m] 算出来, 费时 O(m), 接着我们把这 m
个数排序成一个 array A, 费时 O(m log m). 剩下的就是检查 Y 里面每个元素有没有
出现在 A 里面, 若有则回答 yes, 若完全没有则回答 no.
现在因为 A 已经被排序过, 所以判断 Y 里面任何一个元素在不在 A 里面, 都只要
O(log m) 时间即可 (用 binary search), 所以这步费时 O(n log m).
总共花的时间是
m<=n
O(m) + O(m log m) + O(n log m) ====== O(m log n) + O(n log m).
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 122.124.99.236