如何从遍历两个不相交的等多个顶点集中找到最后一个 egde 连接顶点



给定两个不相交的、等多个(大小为 n)的集合(称为 01),其值从 12n 我必须找到由特定遍历形成的最后一条边(顶点对)。

遍历算法:

  • 从值1开始(此值在哪个集合中无关紧要)
  • 将它与第一个,来自相反集合的自由值连接(第一个相对于实际值,所以如果当前值等于3,那么我将检查4567,...,2n - 12n12
  • 重复第二步

例:

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)的复杂性解决这个问题。但我相信有一个更好的解决方案。

您可以在

O(nlogn)中执行此操作

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

第四步阐述:

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

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

如果你在数组 b 中进行二叉搜索,你将得到的位置是 2 。所以现在——

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

更新:

实现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;
}

最新更新