请教一个算法问题

bood

那你直接分析这种对数的数目以及每种对数出现的概率好了，看看会不会低于m*n
个人表示怀疑

[ 本帖最后由 bood 于 2008-9-1 17:12 编辑 ]

0vk0

O(mn)是算法时间复杂度，并不是指大小

跟感觉上应该有低于O(mn)的算法无关

ychang0918

[quote]原帖由 [i]happy_fish100[/i] 于 2008-9-1 17:00 发表 [url=http://bbs.chinaunix.net/redirect.php?goto=findpost&pid=9180010&ptid=1258770][img]http://bbs.chinaunix.net/images/common/back.gif[/img][/url]


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


int i;
int k;
int dis;

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

感谢happy_fish100。不过感觉好像有点问题。请教一下。如果a[i]...a[j] i<=x<=j<y<n 都满足 min < (a[x]-b[k]) <max 而 max<a[y]-b[k], 此时k++，而i不变，就会漏掉相当一部分了

happy_fish100

有点错误，更正如下：

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


int i;
int k;
int t;
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)
     {
          //输出时采用贪婪原则
          t = i;
          while (t < n && (a[t] - b[k] > -1 * max) && (a[t] - b[k] < -1 * min))
          {
               printf("%d, %d\n", a[t], b[k]);
               t++;
          }

          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)
     {
          //打印时采用贪婪原则
          t = k;
          while (t < m && (a[i] - b[t] > min) && (a[i] - b[t] < max))
          {
               printf("%d, %d\n", a[i], b[t]);
               t++;
          }

          i++;
     }
     else
     {
           k++;
     }
}

ychang0918

感谢happy_fish100

wzcsoft

我的思路是二分查找。

先把一个数组排好序，然后二分查找上下界，位于上下界之间的元素就是我们要的
比如说对于 min<a-b[j]<max    b[j]<a-min   a-min就是上界，我们找a-min这个数
a-max<b[j]  a-max是下界。
对于min<-(a-b[j])<max 这种case一样处理   

当然我们不一定就能找到我们要找的数，但我们可以找到我们要的位置：比如 3 5 8中要找7，找不到，但是可以找到8这个位置

这样的话复杂度是  O(lg(m)+n*lg(m))  好了，欢迎大家来拍砖