【算法】集合运算

算法训练 集合运算

时间限制：1.0s 内存限制：512.0MB

锦囊1

排序后处理。

锦囊2

先排序，对于每个集合的操作，都使用两个指针来指向排序后的集合，对于相同元素特别处理。

问题描述

给出两个整数集合A、B，求出他们的交集、并集以及B在A中的余集。

输入格式

第一行为一个整数n，表示集合A中的元素个数。
第二行有n个互不相同的用空格隔开的整数，表示集合A中的元素。
第三行为一个整数m，表示集合B中的元素个数。
第四行有m个互不相同的用空格隔开的整数，表示集合B中的元素。
集合中的所有元素均为int范围内的整数，n、m<=1000。

输出格式

第一行按从小到大的顺序输出A、B交集中的所有元素。
第二行按从小到大的顺序输出A、B并集中的所有元素。
第三行按从小到大的顺序输出B在A中的余集中的所有元素。

样例输入

5
1 2 3 4 5
5
2 4 6 8 10

样例输出

2 4
1 2 3 4 5 6 8 10
1 3 5

样例输入

4
1 2 3 4
3
5 6 7

样例输出

1 2 3 4 5 6 7
1 2 3 4

当时想偷个懒，以为所有的数据都是在不大的范围内，没想到测试数据有点变态。居然还有负数和很大数据。

当时想到用各个很大的数组装就行了，从而不用排序，不过确实是行得通的，居然以下子就过了80%的数据。

代码：

import java.util.Scanner;

public class 集合运算 {
	
	static int[] data=new int[8836460];
	public static void main(String[] args) {
		
		//System.out.println((int)Math.pow(2, 31)-1);
		Scanner sc=new Scanner(System.in);
		int n=sc.nextInt();
		for (int i = 0; i < n; i++) {
			data[sc.nextInt()]=1;
		}
		
		int m=sc.nextInt();
		for (int i = 0; i < m; i++) {
			data[sc.nextInt()]+=2;
		}
		int co1=0,co2=0;
		for (int i = 0; i < data.length; i++) {
			if(data[i]==3){
				System.out.print(i+" ");
				co1=1;
			}
		}
		if(co1==1)
			System.out.println();
		for (int i = 0; i < data.length; i++) {
			if(data[i]>0){
				System.out.print(i+" ");
				co2=1;
			}
		}
		if(co2==1)
			System.out.println();
		for (int i = 0; i < data.length; i++) {
			if(data[i]==1){
				System.out.print(i+" ");
			}
		}
	}
}