A、B两个整数集合的交集 - BrilliantEagle的专栏 - 博客频道 - CSDN.NET
http://www.cnblogs.com/bestdavid/p/examinationtencent.html
思路3：集合压缩
对于一个集合来说，我们很容易就可以得到集合的最大值和最小值，假设集合A的最大值和最小值分别为MaxInA，MinInA；假设集合B的最大值和最小值分别为MaxInB，MinInB；那么集合A的所有元素一定在闭区间【MinInA, MaxInA】里面，集合B的所有元素一定在闭区间【MinInB, MaxInB】里面，从这两个集合里面我们可以作如下判断：（集合A和集合B都在链表中！此算法使用链表结构，操作起来比数组更方便）
1. 若MinInA == MinInB或者MaxInA == MaxInB，那么MinInA 或者MaxInA （相等的那个数）就一定在交集里面，存入交集（可以用数组存），删除链表中相应的结点；若不想等则跳到第3步；
2. 重新找到集合A和B中的最大值和最小值MinInA 、MaxInA 、MinInB、MaxInB；跳回第1步；
3. 更新区间（交集的区间），区间的更新如下：区间下界为Lower = max(MinInA, MinInB)，上届为Upper = min(MaxInA , MaxInB)，那么剩下的交集一定在闭区间【Lower ,Upper】里面，按照这个区间来剔除掉集合A和集合B中不符合条件的元素，剔除结束后，若其中一个集合为空，跳到第4步，否则返回第2步；
4. 程序结束，退出！
这种适用于集合里面数值比较散乱，最大值最小值差值比较大的情况！算法的思想在于不断减小搜索的范围，时间的消耗主要在查找集合的最大值和最小值上，我们来看一个例子，集合A= {1, 3, 10, 100, 123, 0, 6} ,B = {3, 2, 10, 23, -1},
集合A的闭区间【0， 123】，集合B的区间【-1，23】,交集的闭区间就为【0，23】，按照这个区间，剔除集合A中的｛ 100, 123｝，剔除集合B的｛-1｝，集合A=｛1, 3, 10, 0, 6｝集合B=｛3, 2, 10, 23｝，没有相等的，继续缩小范围，为【2，10】，这时MaxInA == MaxInB，满足条件，把10存入交集数组中，剔除两个集合的结点；集合变为A= ｛3，6｝集合B={3}，满足MinInA == MinInB或者MaxInA == MaxInB，把3存入交集数组中，集合B为空，结束！如图：
用数组来模拟（本质上说集合中是没有重复元素的，这里用数组来模拟可以用重复元素），A、B数组长度分别为m和n。总的来说，分为以下几种方案。
方案1：两重循环判断（复杂度 O（m*n））
暴力方法，并且不容易去除重复元素
方案2:Hash Table方法（复杂度 O（m+n））
将A写入Hash Table，让后B在Hash Tabe中写入过程中判断重复即可。如果没有重复元素，唯一缺点是内存占用量大，可以使用《编程珠玑》中的BitMap方法节省内存。另外Hash过程中可能会有比较多的冲突。
另外，本方法不具有普遍性。
方案3：排序后对A中每个元素在B中进行二分查找（复杂度 O(nlogn+mlogm)）
这里m<=n。否则排序后对B中每个元素在A中进行二分查找（复杂度 O（n*lgm））
注意，排序的复杂度是O(nlogn+mlogm)，查找的复杂度是O（n*lgm）。
方案4：排序后应用归并排序的思想进行判断（复杂度 O(nlogn+mlogm)）
指针i和j分别指向A和B的开头，如果对应元素相等即为交集，否则谁小谁的指针加1往后移动。
http://www.cnblogs.com/bestdavid/p/examinationtencent.html
思路3：集合压缩
对于一个集合来说，我们很容易就可以得到集合的最大值和最小值，假设集合A的最大值和最小值分别为MaxInA，MinInA；假设集合B的最大值和最小值分别为MaxInB，MinInB；那么集合A的所有元素一定在闭区间【MinInA, MaxInA】里面，集合B的所有元素一定在闭区间【MinInB, MaxInB】里面，从这两个集合里面我们可以作如下判断：（集合A和集合B都在链表中！此算法使用链表结构，操作起来比数组更方便）
1. 若MinInA == MinInB或者MaxInA == MaxInB，那么MinInA 或者MaxInA （相等的那个数）就一定在交集里面，存入交集（可以用数组存），删除链表中相应的结点；若不想等则跳到第3步；
2. 重新找到集合A和B中的最大值和最小值MinInA 、MaxInA 、MinInB、MaxInB；跳回第1步；
3. 更新区间（交集的区间），区间的更新如下：区间下界为Lower = max(MinInA, MinInB)，上届为Upper = min(MaxInA , MaxInB)，那么剩下的交集一定在闭区间【Lower ,Upper】里面，按照这个区间来剔除掉集合A和集合B中不符合条件的元素，剔除结束后，若其中一个集合为空，跳到第4步，否则返回第2步；
4. 程序结束，退出！
这种适用于集合里面数值比较散乱，最大值最小值差值比较大的情况！算法的思想在于不断减小搜索的范围，时间的消耗主要在查找集合的最大值和最小值上，我们来看一个例子，集合A= {1, 3, 10, 100, 123, 0, 6} ,B = {3, 2, 10, 23, -1},
集合A的闭区间【0， 123】，集合B的区间【-1，23】,交集的闭区间就为【0，23】，按照这个区间，剔除集合A中的｛ 100, 123｝，剔除集合B的｛-1｝，集合A=｛1, 3, 10, 0, 6｝集合B=｛3, 2, 10, 23｝，没有相等的，继续缩小范围，为【2，10】，这时MaxInA == MaxInB，满足条件，把10存入交集数组中，剔除两个集合的结点；集合变为A= ｛3，6｝集合B={3}，满足MinInA == MinInB或者MaxInA == MaxInB，把3存入交集数组中，集合B为空，结束！如图：
对于第三个方法，我只是把算法的思想做了一下总结，并没有编写代码运行调试并与其他算法做比较！比较过的朋友，欢迎告知三种算法的优劣性！
Read full article from A、B两个整数集合的交集 - BrilliantEagle的专栏 - 博客频道 - CSDN.NET