Question

已知递增有序的单链表 A,B和C分别存储了一个集合设计算法实现 A:=A∪(B∩C),并使求解结构A仍保持递增。

要求算法的时间复杂度为 O(|A|+|B|+|C|)。其中,|A|为集合A 的元素个数。用C语言实现。

Answer 1

#include <stdio.h>
#include <stdlib.h>

int la,lb,lc,lA,lbc,i;
int a[1001],b[1001],c[1001],bc[1001];
int A[1001];

void init()
{
	scanf("%d%d%d",&la,&lb,&lc);
	for (i=1;i<=la;i++) scanf("%d",a+i);
	for (i=1;i<=lb;i++) scanf("%d",b+i);
	for (i=1;i<=lc;i++) scanf("%d",c+i);
}

void work()
{
	int ta,tb,tc,tbc;
	tb=tc=1;
	while (tb<=lb&&tc<=lc)
	{
		if (b[tb]<c[tc])
		{
			while (b[tb]<c[tc]&&tb<=lb) tb++;
		} else {
			while (c[tc]<b[tb]&&tc<=lc) tc++;
		}
		if (tb>lb||tc>lc) break;
		if (b[tb]==c[tc])
		{
			bc[++lbc]=b[tb]; 
			tb++; tc++;
		}
	}
	tbc=1; ta=1;
	while (ta<=la||tbc<=lbc)
	{
		if (ta<=la&&tbc<=lbc&&a[ta]==bc[tbc])
		{
			ta++; tbc++;
			A[++lA]=a[ta-1];
		} else if (ta<=la&&(a[ta]<bc[tbc]||tbc>lbc)) A[++lA]=a[ta++];
		else if (tbc<=lbc&&(bc[tbc]<a[ta]||ta>la)) A[++lA]=bc[tbc++];
	}
}

int main()
{
	init();
	work();
	printf("%d\n",lA);
	for (i=1;i<=lA;i++) printf("%d ",A[i]);
	printf("\n");
}

以上代码，题目中说A，B，C是单链表，那就直接当作数组来做了，反正差不多。

la,lb,lc分别为A，B，C的大小，a，b，c存储其中的元素，A用来存最终的答案。

bc数组存储的是 B∩C 的答案，lbc为 |B∩C| 

思路如下：

首先由于a，b，c都是递增的，所以可以利用它的单调性。

在求 B∩C 时，两个指针分别指向链表头 (tb,tc) 若 b[tb]<c[tc] 那么和c[tc]相等的b集合中的值一定存在tb之后，所以一直将tb指针向后跳，直到b[tb]>=c[tc] 相反的话类似。当得到一个 b[tb]==c[tc] 时，将它加入bc中，两个指针同时向后走一步。显然，由于tb和tc都恰好遍历了整个链一次，所以复杂度 O ( |B|+|C| )

接下来需要做的就是合并两张有序表 a 和 bc，同样两个指针( ta,tbc ) 然后哪个小放哪个，一直到两个指针都到尾端为止，复杂度类似于上一步 O ( |A| + |BC| )

综上，复杂度为 O ( |A| + 2*( |B|+|C| ) ) 2为常数，可以略去