求2个集合的交集

求交集和并集的线性算法(原创） 对于给定的两个集合，使用哈希表可以在线性时间复杂度内得到他们的交集和并集，具体说明如下： 假设有集合A={1, 7, 5, 13, 9, 10, 11}, B={5, 7, 10, 1, 18, 12}, 1)求交集，需要得到结果：A∩B={1, 5, 7,10} 思路如下： ①建立一个哈希表(HashTable)，其键(KEY)表示集合中数字的值，其值(VALUE)表示集合中数字出现的次数 ②遍历集合A，将集合中的每个数字(KEY)插入哈希表，每个数字的出现次数(VALUE)设置为1 ③遍历集合B，对于集合中的每个数字： 如果哈希表中已经存在该数字，将对应的VALUE改为2 如果哈希表中不存在该数字，忽略 ④遍历哈希表，输出VALUE为2的数字，即得到A和B的交集 2) 求并集，需要得到结果：AUB={1,5,7,9,10,11,12,13,18} 思路如下： ①建立一个哈希表(HashTable)，其键(KEY)表示集合中数字的值，其值(VALUE)可以无视 ②遍历集合A，将集合中的每个数字(KEY)插入哈希表 ③遍历集合B，对于集合中的每个数字： 如果哈希表中已经存在该数字，忽略 如果哈希表中不存在该数字，将这个数字插入哈希表 ④遍历哈希表，输出哈希表中的每个KEY，即为A和B的并集 上面以两个集合为例说明了交集和并集的求法，事实上，上述算法可以很方便的扩展到3个或3个以上的集合 的求交集和求并集。另外求并集时，由于哈希表的值（VALUE）部分不需要用到，所以这个数据结构也可以更换为 哈希集（HashSet)。 转载请注明出处。 VB中HashTable 2012-08-20 14:43:21| 分类： asp.net|举报|字号 订阅 首先定义一个hashtable Dim hstl As New Hashtable hstl.Add(key, value) 'java是用.put MS开始全面模仿java 这说说vb.net中的hashtable基本用法： 添加值：hstl.add(key,value) 通过key取值: hstl.Item(key).ToString 判断是否含有Key: ContainsKey(key) 判断是否含有value: ContainsValue(value) 遍历hashtable: Dim de As DictionaryEntry '泛型类 For Each de In hstl console.write(de.key & de.value) Next de hashtable不支持通过value取key. 求2个集合的交集 第一种方法 最简单、粗暴的循环遍历2个集合，判断如果有相同的元素就取出来。假设集合1的长度为M，集合2的长度为N，那么，时间复杂度为：O(M*N) 代码： public static List<string> GetIntersection(List<string> list1, List<string> list2) { List<string> list3 = new List<string>(); //第一种方法：循环遍历 //O(n×m) for (int i = 0; i < list1.Count; i++) { for (int j = 0; j < list2.Count; j++) { if (list1[i]==list2[j]) { list3.Add(list1[i]); } } } return list3; } 第二种方法 利用hash这种很有用的数据结构来实现。我们知道，hash的特点之一就是不允许有重复元素，即hash表中的元素都是唯一的。所以，我们的思路就是：先把第一个集合的所有元素都放进hashSet中，时间复杂度O(M)；再把第二个集合中的元素放进hashSet中，如果有重复元素，就是这2个集合的交集，时间复杂度为O(N)。即总的时间复杂度从O(M*N)降低到了O(M+N)。 代码： public static List<string> GetIntersection2(List<string> list1, List<string> list2) { //第二种方法：hash List<string> list3 = new List<string>(); HashSet<string> hashSet = new HashSet<string>(); foreach (string item in list1) { hashSet.Add(item); } foreach (string item in list2) { if (hashSet.Add(item) == false) { list3.Add(item); } } return list3; } 测试 代码： static void Main(string[] args) { List<string> list1 = new List<string>(); list1.Add("apple"); list1.Add("banana"); list1.Add("pear"); list1.Add("orange"); list1.Add("grape"); List<string> list2 = new List<string>(); list2.Add("nokia"); list2.Add("sumsung"); list2.Add("htc"); list2.Add("apple"); list2.Add("orange"); List<string> list =new List<string>(); //test for two set join //list = TwoSetsIntersection.GetIntersection(list1, list2); list = TwoSetsIntersection.GetIntersection2(list1, list2); foreach (string item in list) { Console.Write(item + "\t"); } } 总结 hash的另一个特点是查找效率为O(1)，惊人的高！ 对于这道题目要是算出来O(M*N)的同学就应该补课了。出来混，迟早要还的。 HashSet<T>类 HashSet<T>类主要是设计用来做高性能集运算的，例如对两个集合求交集、并集、差集等。集合中包含一组不重复出现且无特性顺序的元素。 HashSet<T>的一些特性如下: 1、HashSet<T>中的值不能重复且没有顺序。 2、HashSet<T>的容量会按需自动添加。 构造方法： HashSet()　默认相等比较器创建一个空的新实例。 HashSet(IEnumerable<T> collection)　　把指定集合中的collection中的数据复制到集中 HashSet(IEqualityComparer<T> comparer)　　使用指定的相等比较器创建一个空的新实例 HashSet(IEnumerable<T> collection,IEqualityComparer<T> comparer)　　使用指定的比较器实例化数据，且将指定集合中的元素复制到集合中。 因为HashSet<T>是专门设计来做集合运算的，因此它提供的方法中有不少是和集合运算相关的。 以下给出它的一些常用方法介绍 成员　　　　　　　　类型　　　　　　　　说明 Add　　　　　　　　方法　　　　　　　　将指定的元素添加到集合中 Clear　　　　　　　 方法　　　　　　　　 清空集合中的所有元素 Contains　　　　 方法　　　　　　　　 确定某元素是否在HashSet<T>中 Exists　　　　　　 方法　　　　　　　　 确定HashSet<T>是否包含于指定条件相匹配的元素 ExceptWith　　　　方法　　　　　　　　 从当前HashSet<T>移除指定集合中的所有元素 IntersectWith　　 方法　　　　　　　　修改当前的HashSet<T>对象，以仅包含该对象和指定集合中存在的元素 IsProperSubsetOf　 方法　　　　　　　　确定HashSet<T>对象是否为指定集合的真子集 IsProperSupersetOf 方法　　　　　　　　确定HashSet<T>对象是否为指定集合的真超集 IsSunsetOf　　　　 方法　　　　　　　　 确定HashSet<T>对象是否为指定集合的子集 IsSupersetOf　　　 方法　　　　　　　　 确定HashSet<T>对象是否为指定集合的超集 Remove　　　　　　方法　　　　　　　　 从HashSet<T>对象中移除指定的元素 RemoveWhere　　 方法　　　　　　　　 从HashSet<T>集合中移除与指定谓词所定义的条件相匹配的所有元素 SetEquals　　　　　方法　　　　　　　　 确定HashSet<T>对象与指定的集合中是否包含相同的元素 SynmmetricExceptWith　　方法　　　　 修改当前的HashSet<T>对象，以仅包含该对象或指定集合中存在的元素 TrimExcess　　　　方法　　　　　　　　 将HashSet<T>对象的容量设置为它所包含的元素的实际个数，向上舍入为接近的特性与实现的值。 UnionWith　　　　 方法　　　　　　　　 修改当前的HashSet<T>对象，以包含该对象本身和指定集合中存在的所有元素 给个简单的例子，写不完的，总之记得HashSet<T>主要的作用是用来进行，交集、并集等运算的就OK了。 static void Main(string[] args) { HashSet<string> hs = new HashSet<string>(); hs.Add("你"); hs.Add("好"); hs.Add("吗"); HashSet<string> hs1 = new HashSet<string>(); hs1.Add("你"); hs1.Add("好"); bool b = hs1.IsProperSubsetOf(hs); //确定hs1是否是hs的真子集 Console.WriteLine(b); //输出True HashSet<string> hs2 = new HashSet<string>(); hs2.Add("爱你"); IEnumerable<string> list = hs.Union(hs2); //返回并集 foreach (string str in list) { Console.WriteLine(str); //输出 你 好 吗 爱你 } Console.ReadKey(); }