【题目】
A、B两个整数集合,设计一个算法求他们的交集,尽可能的高效。
【来源】
腾讯2014校招软件开发笔试题目
【思路一】
对集合A和集合B进行排序(升序,用快排,平均复杂度O(N*logN))。
设置两个指针p和q,同时指向集合A和集合B的第一个元素(已经升序排序)。用一个容器vector记录集合的交集。
如果两个元素大小相等的,说明是集合交集元素,加入交集vector中;
如果两个元素大小不相等的,p和q中较小值的指针,指向下一个元素。
依次操作,直到其中一个集合没有元素可比较为止。
排序:O(nlogn)
比较:O(n)
时间复杂度:O(n + nlogn + nlogn)
【代码一】
/*------------------------------------- * 日期:2015-02-03 * 作者:SJF0115 * 题目: 集合交集 * 来源:腾讯 * 博客: ------------------------------------*/ #include <iostream> #include <cstring> #include <vector> #include <algorithm> using namespace std; vector<int> IntersectionSet(vector<int> set1,vector<int> set2){ int size1 = set1.size(); int size2 = set2.size(); // 排序 sort(set1.begin(),set1.end()); sort(set2.begin(),set2.end()); int i = 0,j = 0; vector<int> result; // 比较 while(i < size1 && j < size2){ // 相同的加入差集中 if(set1[i] == set2[j]){ result.push_back(set1[i]); ++i; ++j; }//if // 值小的跳过 else if(set1[i] < set2[j]){ ++i; }//else else{ ++j; }//else }//while return result; } int main(){ vector<int> set1 = {1,22,6,9,11,5}; vector<int> set2 = {2,10,11,4,22,3,15}; vector<int> result = IntersectionSet(set1,set2); for(int i = 0;i < result.size();++i){ cout<<result[i]<<" "; }//for cout<<endl; return 0; }
【思路二】
以空间换时间。把集合(集合里面的元素是不重复的)中的元素作为数组下表的索引。
例如:
{1,22,6,9,11,5}
Have[1] = 1 Have[22] = 1 Have[6] = 1 Have[9] = 1 Have[11] = 1 Have[5] = 1
{2,10,11,4,22,3,15}
在第二个数组遍历时,判断Have[i] == 1,如果等于1说明两个集合都有这个元素,它就是交集元素
如果不想等,继续下一个元素
时间复杂度:O(n) 空间复杂度很大
【代码二】
/*------------------------------------- * 日期:2015-02-03 * 作者:SJF0115 * 题目: 集合交集 * 来源:腾讯 * 博客: ------------------------------------*/ vector<int> IntersectionSet(vector<int> set1,vector<int> set2){ int size1 = set1.size(); int size2 = set2.size(); // 计算最大值元素 int max = 0; for(int i = 0;i < size1;++i){ if(max < set1[i]){ max = set1[i]; }//if }//for for(int i = 0;i < size2;++i){ if(max < set2[i]){ max = set2[i]; }//if }//for int* hash = new int[max+1]; // 初始化为0 memset(hash,0,sizeof(hash)); vector<int> result; for(int i = 0;i < size1;++i){ hash[set1[i]] = 1; }//for // 交集 for(int i = 0;i < size2;++i){ if(hash[set2[i]] == 1){ result.push_back(set2[i]); }//if }//for delete hash; return result; }
【思路三】
思想: 位图标示法
1 遍历 集合A,求出 最值,效率 1.5n ,计算最大值与最小值的差为LA。对B一样求出最值的差为LB。
2 新建一块空间 M,大小为 min( LA, LB ) / 8 取整 +1 个字节
3 遍历 最值差 小的 集合
设置M的第j个比特为1(从0开始),j 为 每个 元素 与 该集合 最小值的差。
设置 第j个比特为1 的方法:使用 unsigned char 指针p 指向 M,*(p+j/8) |= 1 << j%8
4 遍历 另外一个 集合
以 每个元素 与 前一个 集合 最小值的 差 为 k,若 k 小于 0 或 大于 min(LA,LB) 则 该 元素 不属于 交集
再 查看 M 中 第 k 个 比特 是否 为 1,若是 则 该元素 属于 交集 ,否则 不是。