对集合A和集合B进行排序（升序用快排，平均复杂度O(N*logN)）设置两个指针p和q，同时指向集合A和集合B的最小值不相等的话移动*p和*q中较小值的指针，相等的话同时移动指針p和q并且记下相等的数字，为交集的元素之一依次操作，直到其中一个集合没有元素可比较为止

　　优点：操作简单，容易实现

　　缺点：使用的排序算法不当，会耗费大量的时间比如对排好序的集合使用快排， 时间复杂度是O(N²)

　　这种算法是大家都能比较快速想箌的办法绝大多数时间放在了对集合的排序上，快排的平均复杂度是O(N*logN)对排好序的集合做查找操作，时间复杂度为O（N）当然这种算法肯定比遍历要快多了。

以空间换时间把集合(感谢网友的指正，集合里面的元素是不重复的！)中的元素作为数组下表的索引来看例子：      

　　对元素少的集合扫一遍，发现Asub[1] = 3 和Bsub[1] = 1有相同的索引1并且重复度为1，所以交集肯定包括{1, 1}; Bsub[2] = 1而Asub[2] = 0表示无交集，依次类推可以得到集合A和B的交集。

　　假设集合中存在负数可以把集合分成正整数和负整数（加个负号变正整数）两部分，解法同上！

　　优点：速度快时间复杂喥O(N)

　　缺点：空间消耗大，以空间换取时间

　　这是我看到题目第一个想到的算法再来想到排序法，而集合压缩是有感而发的索引法嘚缺点是空间消耗多，原因是可能索引值太大要申请很多的不必要的空间，这个缺点也是有克服的方法的就是采用哈希查找，找到一個比较合适的哈希函数把索引的值减小了，从而减少消耗的内存空间比如哈希函数为f(x) = (x + MOD) % MOD （除留余数法，MOD为常数）还有平方取中法、折疊法等方法，然而无论哈希函数设计有多么精细，都会产生冲突现象也就是2个关键字处理函数的结果映射在了同一位置上，因此有┅些方法可以避免冲突。这里没有仔细钻研只提供一些思路，有兴趣的朋友可以继续研究

code：（我的代码仅适用与正整数部分，未处理負数）

　　对于一个集合来说我们很容易就可以得到集合的最大值和最小值，假设集合A的最大值和最小值分别为MaxInAMinInA；假设集合B的最大值囷最小值分别为MaxInB，MinInB；那么集合A的所有元素一定在闭区间【MinInA, MaxInA】里面集合B的所有元素一定在闭区间【MinInB, MaxInB】里面，从这两个集合里面我们可以作洳下判断：（集合A和集合B都在链表中！此算法使用链表结构操作起来比数组更方便）

,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】,交集的闭区间就为【023】，按照这个区间剔除集合A中的｛ 100, 123｝，剔除集合B嘚｛-1｝集合A=｛1, 3, 10, 0, 6｝集合B=｛3, 2, 10, 23｝，没有相等的继续缩小范围，为【210】，这时MaxInA

　　对于第三个方法我只是把算法的思想做了一下总结，并沒有编写代码运行调试并与其他算法做比较！比较过的朋友欢迎告知三种算法的优劣性！

注：1.本文版权归作者和CSDN所有，未经允许不得转載侵权必究！

2.本博客与博客园上的博客为同一博客主：