整数集和求并

腾讯研发2013年笔试题最后一题

A，B两个整数集合，设计一个算法求他们的交集，尽可能的高效。

思路1：老老实实查询，对A集合中的每一个元素在B集合中查找，找到则加入并集，时间复杂度O(mn)，正确但不高效。

思路2：再审题分析，由于是集合，说明元素不重复，而整数又是个很舒服的数据结构，假设限定在C语言里的整数范围（其他情况类似），用4个Byte表示[-2^31,2^31)，可以考虑使用位图法做hash，即用2^32位来对应2^32个整数。算法思路：申请2^32位共512M内存对A中的每个整数做hash，在位图中把与其对应的位置1。对B中的每个元素检查位图对应的位，如果为1则加入并集。

时间复杂度O(m+n)，空间换时间，貌似代价略大，可以考虑更换hash，允许一定概率的碰撞。

一个简单的位图实现方法：

 1 #include<stdio.h>
 2 #define MAXN 100
 3 unsigned char hash[1<<29]={0};//注意大数组在局部中会申请失败
 4 int main()
 5 {
 6     int i,m,n,k=0;
 7     int A[MAXN]={0};
 8     int B[MAXN]={0};
 9     int intersection[MAXN]={0};
10     printf("hello
");
12     scanf("%d %d",&m,&n);
13     for(i=0;i<m;i++){
14         scanf("%d",&A[i]);
15         hash[((unsigned) A[i])/8] += 0x80 >> ((unsigned)A[i] % 8);
17     }
18     for(i=0;i<n;i++){
19         scanf("%d",&B[i]);
21         if(0 != (hash[((unsigned) B[i])/8] & (0x80 >> ((unsigned)B[i] % 8)))){
22             intersection[k]=B[i];
23             k++;
24         }
25     }
26     for (i=0;i<k;i++)
27         printf("%d ",intersection[i]);
28     printf("
");
29     return 0;
30 }

扩展一下，如果是大数据下的多个集合求并集，不限元素类型，那么最好采用hash链表，为表中的每个节点设置计数器即可。当然也可以两两求并，不过效率貌似不如前者。