编程题：给定两个集合，求两个集合的交集

题目：给定两个整数集合，求两个集合的交集。

法一：排序法（先将集合排序，在找交集）

            排序时间复杂度O（nlogn)，对集合遍历查找O(n)；总的时间复杂度O(nlogn)；

void main()
{
	int a[] = { 1, 5, 9, 8, 6, 4 };
	int b[] = { 9, 4, 2, 0, 5, 11, 12 };
	int alen = sizeof(a) / sizeof(int);
	int blen = sizeof(b) / sizeof(int);
	sort(a, a + alen);//排序
	sort(b, b + blen);
	vector<int> res; //保存结果
	if (a[0] > b[blen - 1] || b[0] > a[alen - 1])
		return;
	
	int i = 0,j = 0;
	while (i < alen &&j < blen) //查找
	{
		if (a[i]>b[j])
			j++;
		else if (a[i] < b[j])
			i++;
		else
		{
			res.push_back(a[i]);
			cout << a[i] << "  ";
			i++; j++;
		}
	}
	cout << endl;
}

  法二：位图法（很巧妙啊）

时间复杂度：O(n) ,空间复杂度取决于最短数组的最大值和最小值差O((max-min)/32)；

void AndNums(int* a, int* b, int alen, int blen)
{
	int min = 0, max = 0;
	int *ps = NULL, *pl = NULL;
	int len = 0, longlen = 0;
	if (alen < blen)
	{
		ps = a;
		len = alen;
		longlen = blen;
		pl = b;
	}
	else
	{
		ps = b;
		len = blen;
		longlen = alen;
		pl = a;
	}
	min = max = ps[0];
	for (int i = 1; i < len; ++i)
	{
		if (ps[i] < min)
			min = ps[i];
		if (ps[i]>max)
			max = ps[i];
	}
	int gap = max - min;
	gap = gap / 32 + 1; //存储差值要gap个int 类型的数
	int *extra = new int[gap];
	for (int i = 0; i < gap; ++i) extra[i] = 0;
	int outInd, inInd;
	for (int i = 0; i < len; ++i)
	{
		outInd = (ps[i] - min) / 32;
		inInd = (ps[i] - min) % 32;
		extra[outInd] |= 1 << inInd;
	}
	vector<int> res;
	for (int i = 0; i < longlen; ++i)
	{
		if ((pl[i] - min >= 0) && (pl[i] - min <= max - min))
		{
			outInd = (pl[i] - min) / 32;
			inInd = (pl[i] - min) % 32;
			if (0 != (extra[outInd] & (1 << inInd)))
			{
				res.push_back(pl[i]);
				cout << pl[i] << endl;
			}	
		}
	}
	cout << endl;
}
void main()
{
	int a[] = { 1, 5, 9, 8, 6, 4 };
	int b[] = { 9, 4, 2, 0, 5, 11, 12 };
	int alen = sizeof(a) / sizeof(int);
	int blen = sizeof(b) / sizeof(int);
	AndNums(a, b,alen,blen);
}

这种位图法，其实在空间要求不高的情况下，还有一种解法；

开始时A[max]=B[max]={0};

A={ 1 5 9 8 6 4}；则令 A[1]=1  A[5]=1  A[9]=1 A[8]=1 A[6]=1 A[4]=1

然后遍历B i=1:lenth，判断A[ B[i] ]是否为1，若是，则为交集，反之就不是；（但是，这种方法，当元素值为负数的时候就不好办了）

法三：集合压缩法：见网址：http://blog.csdn.net/jie1991liu/article/details/13168255