請教一個算法問題

bood

那你直接分析這種對數(shù)的數(shù)目以及每種對數(shù)出現(xiàn)的概率好了，看看會不會低于m*n
個人表示懷疑

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

0vk0

O(mn)是算法時間復(fù)雜度，并不是指大小

跟感覺上應(yīng)該有低于O(mn)的算法無關(guān)

ychang0918

[quote]原帖由 [i]happy_fish100[/i] 于 2008-9-1 17:00 發(fā)表 [url=http://72891.cn/redirect.php?goto=findpost&pid=9180010&ptid=1258770][img]http://72891.cn/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不變，就會漏掉相當(dāng)一部分了

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

我的思路是二分查找。

先把一個數(shù)組排好序，然后二分查找上下界，位于上下界之間的元素就是我們要的
比如說對于 min<a-b[j]<max    b[j]<a-min   a-min就是上界，我們找a-min這個數(shù)
a-max<b[j]  a-max是下界。
對于min<-(a-b[j])<max 這種case一樣處理   

當(dāng)然我們不一定就能找到我們要找的數(shù)，但我們可以找到我們要的位置：比如 3 5 8中要找7，找不到，但是可以找到8這個位置

這樣的話復(fù)雜度是  O(lg(m)+n*lg(m))  好了，歡迎大家來拍磚