EI judge 002 Set Intersection 算法题解

Set Intersection

Time limit = 5 second(s)

Memory limit = 33000 Kb

Your task is to find the intersection of two sets of positive integers.

InputThe input consists of two sets of positive integersA={a₁,a₂, ...,a_n} andB={b₁,b₂, ...,b_k} represented as two whitespace-separated lists of numbers. Each list ends with -1, that serves as an end-of-set marker. Repetitions of elements are possible in the input, but not in the output. You may assume that 0 <a_i,b_i<10⁶and that the setsAandBare of size less than 1000.

Outputis list of numbers or word "empty" if intersection is empty.

Input#1 6 7 8 1 2 3 -1 4 3 2 1 1 -1

Output#1 1 2 3

Input#2 1 2 3 -1 4 4 5 5 6 6 -1

Output#2 empty

注意地方：

1 防止重复 -- 这里使用set，第二次遍历数组的时候，记得把set重的数据erase掉

2 输出格式这个oj也很严格的，不能多一个空格

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;

int A[1000] = {0};

void SetIntersection()
{
	set<int> si;
	int a = 0;
	while (cin>>a && -1 != a)
	{
		si.insert(a);
	}

	int j = 0;
	while (cin>>a && -1 != a)
	{
		if (si.count(a))
		{
			A[j++] = a;
			si.erase(a);
		}
	}
	if (!j) cout<<"empty";
	else
	{
		j--;
		for (int i = 0; i < j; i++)
		{
			cout<<A[i]<<' ';
		}
		cout<<A[j];//原来要防止多输出一个' '
	}
}