作者yauhh (哟)
看板CSSE
标题Re: [问题] 未排序的阵列，演算法相关问题
时间Sun May 9 10:35:19 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
: use less than O(m*n) running time
: 我想请问这题大致上从哪方面下手会比较简易
: 谢谢
类似merge sort
ix_ = 0, iy_ = 0;
if (X[ix_]+Y[iy_] != d) {
ix = 1; iy = 1;
while (ix != length(X) && iy != length(Y)) {
int c;
if (X[ix_]+Y[iy_] < d) {
while (X[ix] <= X[ix_] && ix < length(X)) ix++;
while (Y[iy] <= Y[iy_] && iy < length(Y)) iy++;
c = near(X[ix]-X[ix_], Y[iy]-Y[iy_], d-X[ix_]-Y[iy_]);
// Find which of arg 1 and arg 2 is near arg3
if (c == X[ix]-X[ix_])
ix_ = ix;
else // c == Y[iy]-Y[iy_]
iy_ = iy;
} else { // X[ix_]+Y[iy_] > d
while (X[ix] >= X[ix_] && ix < length(X)) ix++;
while (Y[iy] >= Y[iy_] && iy < length(Y)) iy++;
c = near(X[ix_]-X[ix], Y[iy_]-Y[iy], X[ix_]+Y[iy_]-d);
if (c == X[ix_]-X[ix])
ix_ = ix;
else // c == Y[iy_]-Y[iy]
iy_ = iy;
}
if (X[ix_]+Y[iy_] == d) break;
}
}
if (X[ix_]+Y[iy_] == d)
output(ix_, iy_);
else
echo("No solution");
===============================
___Update 05/09 12:59, 15:55___ 重写个演算法
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 ix and iy both maks d' nearer to d than ix_ and ix_,
ix_ = ix, iy_ = iy, ix = ix+1, iy = iy+1.
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
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 218.160.209.141
1F：推 FRAXIS:X和Y不用sort吗？ 05/09 11:55
2F：→ yauhh:题目说两个是unsorted. 05/09 12:03
3F：→ yauhh:可能做太快了,跳过好几个case,我再检查一下. 05/09 12:04
4F：→ yauhh:喔,类似merge sort是指程式结构类似merge sort,不是真做排序 05/09 12:35
※ 编辑: yauhh 来自: 218.160.109.216 (05/09 15:56)