joj:1011 If only I had a Venn diagram--求集合的差集

1011: If only I had a Venn diagram

---

Result TIME Limit MEMORY Limit Run Times AC Times JUDGE

	3s	524288K	3842	1528	Standard

The symmetric difference of two sets is the set of elements belonging to one but not both of the two sets. For example, if we have two sets A = {1,2,3,4,5} and B = {3,4,5,6,7,8}, then the symmetric difference of A and B is the set {1,2,6,7,8}.

Given two sets of positive integers, display their symmetric difference.

Input

 

A positive integer will denote the number of cases. Both sets will be input from a single line. A zero (0) marks the end of each set. There will be no more than 20 numbers in each set, and no number within a set will be repeated. Each number in a set is a positive integer less than 65535.

Output

 

The set of integers making up the symmetric difference of the two sets. The numbers within a set may be sorted from smaller to bigger.

Sample Input

3 1 2 3 4 5 0 3 4 5 6 7 8 0 1 2 3 0 1 2 3 0 129 34 5 6 7 0 129 0

Sample Output

{1,2,6,7,8} {} {5,6,7,34}

 

 

 

/*
关键思路是找两个集合的差集
两种方法。。
*/
#include <stdio.h>
int a[100];
int b[100];
int res[100];
/*
选择排序
*/
void sortBySelect2(int *array,int len)
{
	for(int i=0;i<len - 1;i++)
	{
		int t = 0;
		int tmp;
		for(int j=i;j<len;j++)
		{
			if(array[j] < array[i])
			{
				t = j;
				tmp = array[i];
				array[i] = array[t];
				array[t] = tmp;
			}				
		}
		
	}
}
/*
错误的选择排序
*/
void sortBySelect(int *array,int len)
{
	for(int i=0;i<len - 1;i++)
	{
		int t = 0;
		int tmp;
		for(int j=i;j<len;j++)
		{
			if(array[j] < array[i])
				t = j;
		}
		tmp = array[i];
		array[i] = array[t];
		array[t] = tmp;
	}
}
/*
两个元素中的相同元素被设置成 -1,除去两个集合中的相同元素，剩下的就是不同元素
*/
void reversDifference(int len1,int len2)
{
	int i;
	for(i=0;i<len1;i++)
	{
		for(int j=0;j<len2;j++)
		{
			if(a[i] == b[j])
			{
				a[i] = -1;
				b[j] = -1; 
			}
		}
	}	
	int k = 0;
	i = 0;
	for(i=0;i<len1;i++)
	{
		if(a[i] == -1)
			continue;
		res[k] = a[i];
		k++;
	}
	for(i=0;i<len2;i++)
	{
		if(b[i] == -1)
			continue;
		res[k] = b[i];
		k++;
	}
	if(k == 0)
	{
		printf("{}\n");
		return;
	}
	sortBySelect2(res,k);
	printf("{");
	for(i=0;i<k-1;i++)
		printf("%d,",res[i]);
	printf("%d}\n",res[i]);
}
/*
这种思路是找两个集合的不同元素，得找两次
所以的两次双重循环
*/
void difference(int len1,int len2)
{
	int k = 0;
	int i;
	for(i=0;i<len1;i++)
	{
		int j;
		for(j=0;j<len2;j++)
		{
			if(a[i] == b[j])
				break;
		}
		if(j >= len2)
		{
			res[k] = a[i];
			k++;
		}
	}
	for( i=0;i<len2;i++)
	{
		int j;
		for( j=0;j<len1;j++)
		{
			if(b[i] == a[j])
				break;
		}
		if(j >= len1)
		{
			res[k] = b[i];
			k++;
		}
	}
	for(int m=0;m<k;m++)
		printf("%d,",res[m]);
	printf("}\n");
}
int main()
{
	int time;
	scanf("%d",&time);
	for(int k=0;k<time;k++)
	{
		int i = 0;
		while(scanf("%d",&a[i]),a[i])
			i++;
		
		int j = 0;
		while(scanf("%d",&b[j]),b[j])
			j++;
		//difference(i , j );
		reversDifference(i,j);
	}
	return 0;
}