腾讯研发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\n"); 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("\n"); 29 return 0; 30 }
扩展一下，如果是大数据下的多个集合求并集，不限元素类型，那么最好采用hash链表，为表中的每个节点设置计数器即可。当然也可以两两求并，不过效率貌似不如前者。
原文：http://www.cnblogs.com/solarya/p/3655401.html