[经典面试题][腾讯]集合差集-白红宇

【题目】

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 
    
         #include 
     
          #include 
      
           #include 
       
            using namespace std;    vector
        
          IntersectionSet(vector
         
           set1,vector
          
            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
           
             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
            
              set1 = {1,22,6,9,11,5}; vector
             
               set2 = {2,10,11,4,22,3,15}; vector
              
                result = IntersectionSet(set1,set2); for(int i = 0;i < result.size();++i){ cout<
               
                <<" "; }//for cout<

【思路二】

以空间换时间。把集合(集合里面的元素是不重复的)中的元素作为数组下表的索引。

例如：

{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
    
      IntersectionSet(vector
     
       set1,vector
      
        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
       
         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，若是则该元素属于交集，否则不是。