求2个集合的交集

第一种方法

最简单、粗暴的循环遍历2个集合，判断如果有相同的元素就取出来。假设集合1的长度为M，集合2的长度为N，那么，时间复杂度为：O(M*N)

代码：

public static List
     
       GetIntersection(List
      
        list1, List
       
         list2){    List
        
          list3 = new List
         
          ();    //第一种方法：循环遍历    //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
     
       GetIntersection2(List
      
        list1, List
       
         list2){    //第二种方法：hash    List
        
          list3 = new List
         
          ();    HashSet
          
            hashSet = new HashSet
           
            (); 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
     
       list1 = new List
      
       ();    list1.Add("apple");    list1.Add("banana");    list1.Add("pear");    list1.Add("orange");    list1.Add("grape");    List
       
         list2 = new List
        
         ();    list2.Add("nokia");    list2.Add("sumsung");    list2.Add("htc");    list2.Add("apple");    list2.Add("orange");    List
         
           list =new List
          
           (); //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)的同学就应该补课了。出来混，迟早要还的。