作者willhunting (这些年来)
看板CSSE
标题Re: [问题] 未排序的阵列，演算法相关问题
时间Sun May 9 00:59:12 2010
※ 引述《Hatred (yo)》之铭言：
: ※ 引述《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).
Hatred的这个作法不错，不过你最後的complexity应该是O(m log m) + O(n log n)
我也有一个作法:
先排序X再排序Y: O(m log m) + O(n log n)
然後下一步比较妙
排序後的X:
x[0] x[1] x[2] ... x[m-1]
排序後的Y:
y[0] y[1] y[2] ... y[n-1]
建两个index，x-index一开始指x[0], y-index指y[n-1]
然後查看此两数的和
while(x-index < m && y-index < n)
{
sum = x[x-index] + y[y-index]
if sum > d
--y-index
else if sum = d
current x and y element is a pair which meets the condition
else
++x-index
}
这个方法可能不是很直觉，但其实是正确的。那个回圈的complexity
会是O(m)+O(n)，其实正确来讲是最大为m+n，两个array顶多被整个iterate
一次而已。
所以complexity仍是O(m log m) + O(n log n)。
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 74.68.114.250
1F：→ LPH66:他的後一步是 for all y in Y search y in X 05/09 01:50
2F：→ LPH66: A 05/09 01:50
3F：→ LPH66:所以後面是 O(n log m) 无误 05/09 01:50
4F：→ willhunting:对 我打错了 只有第一个是O(m log m) 05/09 03:23