给定两个不相交的、等多个(大小为 n
)的集合(称为 0
和 1
),其值从 1
到 2n
我必须找到由特定遍历形成的最后一条边(顶点对)。
遍历算法:
- 从值
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)
的复杂性解决这个问题。但我相信有一个更好的解决方案。
您可以在
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;
}