Description
给定两个整数可重复集合,求两个集合的交集。
Input
输入有两组数据,第一组的第一行为一正整数n,一下n个正整数ai(0 < i <= n)。
第二组的第一行为正整数m,以下m个正整数bi(0 < i <= m)。
其中 1 < n, m <= 32767 0 < ai, bi <= 32767
Output
输出一行,k个正整数,为两组数据构成集合{ai}和{bi}的交集。
输出按第二组数据出现的顺序输出,两数之间使用空格间隔,最后一个数无空格,重复数据只输出一次。
若交集为空,只输出一个0
Sample Input
10
1 2 3 4 5 6 7 8 9 10
10
9 10 11 12 13 14 15 16 17 1
Sample Output
9 10 1
时间超限,时间复杂度为o(n),该怎么改呢
#include <iostream>
using namespace std;
int main()
{
int a[32768], b[32768], A[32768]={0}, c,d, e = 0;
cin >> c;
for (int i = 0; i < c; i++)
{
cin >> a[i];
A[a[i]] = 1;
}
cin >> d;
for (int i = 0; i < d; i++)
{
cin >> b[i];
}
for (int i = 0; i < d; i++)
{
if (A[b[i]] == 1)
{
if (e != 0)
{
cout << " ";
}
e++;
cout<< b[i];
}
}
if (e == 0)
{
cout << e;
}
return 0;
}