数据结构实例（Intersection）容易

题目：

计算两个数组的交：

C#自带Function：

Intersect()交集    Except()差集   Union()并集。

本文考察算法哈：

自带的Buff咱不考虑。

1.遍历输出，两次for循环。O（n^2）.最简单，时间复杂度太大

2.先排序，再利用下标循环。O（nlogn）.

3.同时遍历两个数组，放入一个新的容器。把重复的提出来即可。

4.在3的基础上我们可以引申出利用一些特殊集合更完美实现。HASH以及Dictionary。

*先把一个数组全部放进一个容器中，注意：Key不能重复（唯一），否则抛异常。

*我们也恰恰利用这个特性：哈希碰撞/字典碰撞 查重。

*当然我们也可以利用这些容器的Contains（）查重，效率也很快。

感觉自己屌屌的有木有：

 public static List<int> Intersection(int[] nums1, int[] nums2)
        {
            var dicIntersect = new Dictionary<int, int>();
            var intersectData = new List<int>();
            // Traverse the first array.
            foreach (int data in nums1)
            {
                if (!dicIntersect.Keys.Contains(data))
                {
                    dicIntersect.Add(data, 0);
                }

                dicIntersect[data]++;
            }

            // Traverse the second array.  
            foreach (int data in nums2)
            {
                /* Repeat the matched elements */
                if (dicIntersect.Keys.Contains(data))
                {
                    intersectData.Add(data);
                }
                /* dictionary collision */
                try
                {
                    dicIntersect.Add(data,data);
                }
                //An item with the same key has already been added.
                    //发生字典碰撞捕获异常：说明重复Key出现，加入到List即为重复数据
                catch (Exception ex)
                {
                    intersectData.Add(data);
                }
                dicIntersect[data]++;
            }
 
            return intersectData;
         
        }

*************************************************分割线************************************************************

求两个集合的交集。

上题所述返回所有元素。下面来讨论如何返回一个集合。

集合：

确定性（集合中的元素必须是确定的）

互异性（集合中的元素互不相同）

无序性（集合中的元素没有先后之分）

public static Dictionary<int,int> Intersection(int[] nums1, int[] nums2)
        {
            var dicIntersect = new Dictionary<int, int>();
            var intersectData = new Dictionary<int, int>();
            // Traverse the first array.
            foreach (int data in nums1)
            {
                if (!dicIntersect.Keys.Contains(data))
                {
                    dicIntersect.Add(data, 0);
                }

                dicIntersect[data]++;
            }
       
            // Traverse the second array.  
            foreach (int data in nums2)
            {
               
                /* dictionary collision */
                try
                {
                    dicIntersect.Add(data, data);
                }
                    //An item with the same key has already been added.
                    //发生字典碰撞捕获异常：说明重复Key出现，加入到Intersect即为重复数据
                catch (Exception ex)
                {
                    try
                    {
                        intersectData.Add(data, data);
                    }
                    catch (Exception e)
                    {
                        Console.WriteLine("Collection Repeat！");
                    }
                }
                dicIntersect[data]++;
            }

            return intersectData;
        }

我们这里利用C# 异常处理机制来展示这个思路，并不是一个最佳编程实践。

*Dictionary和HASH都具有一个特性：Key唯一。利用此特性我们重复添加元素就会抛异常。那么重复的元素就是我们所求。

除了利用匹配Key值是否唯一还可以利用Contains（）也可以达到目的。