[经典面试题][腾讯]集合差集

【题目】

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，若是 则 该元素 属于 交集 ，否则 不是。