0

给定两个不相交的等数（大小n）集合（称为0and 1），其值从1to2n我必须找到由特定遍历形成的最后一条边（顶点对）。

遍历算法：

  • 从值开始1（这个值在哪个集合中并不重要）
  • 将它与来自相反集合的第一个自由值连接（首先相对于实际值，所以如果当前值等于3，那么我将检查4, 5, 6, 7, ..., 2n - 1, 2n, 1, 2）
  • 重复第二步

例子：

n = 5
Set "0": { 1, 2, 4, 8, 9 }
Set "1": { 3, 5, 6, 7, 10 }

Traversal path:
1 -> 3 -> 4 -> 5 -> 8 -> 10 -> 2 -> 6 -> 9 -> 7

Answer -> 9 and 7

我能够以2 * (1 + 2 ... + n) = 0(n^2)复杂的方式解决这个问题。但我相信有更好的解决方案。

4

1 回答 1

1

你可以这样做O(nlogn)

  • 首先对数组和集合进行排序current = 1
  • 现在找到哪个数组包含 1，因为您必须从值 1 开始
  • 现在current value使用 O(logn) 中的二进制搜索来搜索对面数组（附近）中的位置
  • 找出左右附近值的差值，将当前值更改为差值最小的值
  • 当然，设置您已经使用过的所有访问过的值。这样您就不会以相同的值工作两次
  • 所以整体复杂度是O(nlogn)

第四步细化：

假设您的当前值在array a并且您正在搜索array b...

current value = 5  
b = { 2 , 3 , 8 , 10}  
            ^

如果你在数组b中进行二进制搜索，你会得到的位置是2. 所以现在——

设置current value = 8并将 8 标记为已访问。
现在做step 2 and 3inarray a等等...

更新 ：

示例 C++ 实现：

#include <bits/stdc++.h>
using namespace std;

vector<int>right_a,right_b;
// Using union_find algorithm to find the next available value(which is not visited)
int find1(int x)
{
    if(x==right_a[x])
      return x;
    right_a[x]=find1(right_a[x]);
}
int find2(int x)
{
    if(x==right_b[x])
      return x;
    right_b[x]=find2(right_b[x]);
}
int main()
{
    int i,j,k,l,m,n=5;

    int a[]={1, 2, 4, 8, 9};
    int b[]={3, 5, 6, 7, 10};

    for(i=0;i<n;i++)
    {
        right_a.push_back(i);
        right_b.push_back(i);
    }

    int cur=1,work_with;
    if(a[0]==cur)
    {
        right_a[0]=1;
        work_with=0;
    }
    else
    {
        right_b[0]=1;
        work_with=1;
    }

    printf("%d",1);
    int cnt=1;
    while(cnt<2*n)
    {
        if(work_with==0)
        {
            // find first relative to actual value in array b
            int ind=lower_bound(b,b+n,cur)-b;
            if(ind==n)
              ind=0;
            ind=find2(ind);
            int next=ind+1;
            if(next==n)
                next=0;
            right_b[ind]=right_b[next]; // making current value visited
            printf(" -> %d",b[ind]);
            cur=b[ind];

            work_with=1;
        }
        else
        {
            // find first relative to actual value in array a
            int ind=lower_bound(a,a+n,cur)-a;
            if(ind==n)
              ind=0;
            ind=find1(ind);
            int next=ind+1;
            if(next==n)
                next=0;
            right_a[ind]=right_a[next]; // making current value visited
            printf(" -> %d",a[ind]);
            cur=a[ind];

            work_with=0;
        }
        cnt++;
    }
    printf("\n");
return 0;
}
于 2014-12-29T07:30:43.690 回答