請教一個算法問題

ychang0918

兩個正整數(shù)數(shù)組a[n], b[m]，找出所有差的絕對值在0<min<max之間的所有成對元素，即min<abs(a[i]-b[j])<max。

感覺上應(yīng)該有低于O(mn)的算法。請教大家了。

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

cugb_cat

又出現(xiàn)[i ]了，樓主整理一下吧，真亂。

ychang0918

感謝ls整理好了

happy_fish100

如果兩個數(shù)組是拍好序的，有優(yōu)化算法，可以低于O(mn)。
如果沒有排好序，恐怕只能O(mn)了？

ychang0918

排序不是問題。ls能講講如何實(shí)現(xiàn)嗎？

ychang0918

是動態(tài)規(guī)劃嗎？

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 發(fā)表 [url=http://72891.cn/redirect.php?goto=findpost&pid=9179439&ptid=1258770][img]http://72891.cn/images/common/back.gif[/img][/url]
排序不是問題。ls能講講如何實(shí)現(xiàn)嗎？ [/quote]

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


int i;
int k;
int dis;

//先找相減小于0的匹配項(xiàng)
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的匹配項(xiàng)，和上面的算法類似
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++;
     }
}