请教一个算法问题

ychang0918

两个正整数数组a[n], b[m]，找出所有差的绝对值在0<min<max之间的所有成对元素，即min<abs(a[i]-b[j])<max。

感觉上应该有低于O(mn)的算法。请教大家了。

[[i] 本帖最后由 ychang0918 于 2008-9-1 16:04 编辑 [/i]]

cugb_cat

又出现[i ]了，楼主整理一下吧，真乱。

ychang0918

感谢ls整理好了

happy_fish100

如果两个数组是拍好序的，有优化算法，可以低于O(mn)。
如果没有排好序，恐怕只能O(mn)了？

ychang0918

排序不是问题。ls能讲讲如何实现吗？

ychang0918

是动态规划吗？

bood

不可能
考虑最坏情况max(a)<min(b)，并且min<min(b)-max(a)<max，同时还有min<max(b)-min(a)<max
则任意的ai, bj都是满足条件的对，光是一一列举就要m*n了

cugb_cat

想不出低于O(mn)的算法，DP或许可以，不过理不太清楚思路。

ychang0918

这个也只是最坏mn吧，如果能够平均小于mn也是不错的啊。

happy_fish100

[quote]原帖由 [i]ychang0918[/i] 于 2008-9-1 16:22 发表 [url=http://bbs.chinaunix.net/redirect.php?goto=findpost&pid=9179439&ptid=1258770][img]http://bbs.chinaunix.net/images/common/back.gif[/img][/url]
排序不是问题。ls能讲讲如何实现吗？ [/quote]

如果a[n]和b[m]是升序排列的，算法如下：


int i;
int k;
int dis;

//先找相减小于0的匹配项
i = 0;
k = 0;
while (i < n && k < m)
{
    dis = a[i] - b[k];
    if (dis >= 0)
    {
         k++;
         continue;
    }

     if (dis > -1 * min)
     {
           k++;
     }
     else if (dis > -1 * max)
     {
          printf("%d, %d\n", a[i], b[k]);
          k++;
     }
     else
     {
          i++;
     }
}

//再找相减大于0的匹配项，和上面的算法类似
i = 0;
k = 0;
while (i < n && k < m)
{
    dis = a[i] - b[k];
    if (dis <= 0)
    {
         i++;
         continue;
    }

     if (dis < min)
     {
           i++;
     }
     else if (dis < max)
     {
          printf("%d, %d\n", a[i], b[k]);
          i++;
     }
     else
     {
           k++;
     }
}