算法学习笔记之两个数组取交集

题目：给定两个数组，编写一个函数来计算它们的交集。

int[] arr1 = {1,1,2,3,4};
int[] arr2 = {2,3};
.
.
method(arr1,arr2);
.
.
输出：2,3

打印输出的结果。

解题思路：

取交集就是取两个数组里面的相同的元素，如果数组里面元素有重复，先去重。思路有了接下来就是代码实现了，这里先提供一种常规的写法，既然是两个数组里面的元素，那么首先想到的就是双重for循环去遍历两个数组，把相同的元素放到一个集合里面，最后对集合进行排序，然后打印数据。

private static void method1(int[] array1 ,int[] array2){
    ArrayList<Integer> listTemp = new ArrayList<>();
    for (int array1Element : array1) {
        for (int array2Element : array2) {
            if (array1Element == array2Element) {
                if (!listTemp.contains(array1Element)) {
                    listTemp.add(array1Element);
                    break;
                }
            }
        }
    }
    if (listTemp.size() == 0) {
        System.out.println("两个数组没有交集");
        return;
    }
    Collections.sort(listTemp);
    StringBuffer sb = new StringBuffer();
    for (int i : listTemp) {
        sb.append(i + ",");
    }
}

一般来说代码写到这里就可以结束了，因为功能已经实现，但是作为一个有责任的开发，肯定是要对自己写的代码的性能做测试，题主测试了一下：100个10以内的数字，方法耗时1ms，1000个10以内的数字耗时11ms，10000个10以内的数耗时398ms，所以数组的长度越大，耗时就越多，显然这样的方法不是最好的方法，那么就要分析一下耗时的原因在哪里，上log。

//通过log发现最为耗时的代码是这一区域的代码
if (!listTemp.contains(array1Element)) {
    listTemp.add(array1Element);
    break;
}               

第一感觉应该是那个contains方法比较耗时，阅读源码看看

//先是add方法
public boolean add(E e) {
    //扩容
   ensureCapacityInternal(size + 1);  // Increments modCount!!
   //赋值
   elementData[size++] = e;
   return true;
}

//contains方法调用了indexof方法
public boolean contains(Object o) {
   return indexOf(o) >= 0;
}

//indexOf方法最后也是循环遍历
public int indexOf(Object o) {
    if (o == null) {
        for (int i = 0; i < size; i++)
            if (elementData[i]==null)
                return i;
    } else {
        for (int i = 0; i < size; i++)
            if (o.equals(elementData[i]))
                return i;
    }
    return -1;
}

到这里就真相大白了，add方法应该是不耗时的，耗时的还是contains方法，因为里面还有一层循环，而且集合越大，循环次数越多，时间复杂度为O(n)，在加上外层的双For循环，整个函数的时间复杂度为O（n^3），所以现在需要解决的核心问题就变成：时间复杂度低的集合查询元素的方法。

常见时间复杂度排序为O(1)< O(logn)< O(n)< O(n^2) 什么是时间复杂度参考这篇文章 ，ArrayList.contains()的时间复杂度为O(n),那么我们就需要一个时间复杂度为O(1)或者O(logn)的方法，我们来看看HashMap。

• HashMap的containsValue方法

public boolean containsValue(Object value) {
    Node<K,V>[] tab; V v;
    if ((tab = table) != null && size > 0) {
        for (int i = 0; i < tab.length; ++i) {
            for (Node<K,V> e = tab[i]; e != null; e = e.next) {
                if ((v = e.value) == value ||
                    (value != null && value.equals(v)))
                    return true;
            }
        }
    }
    return false;
}

遍历数组里先得到头节点，然后再遍历链表得到value，间复杂度是O(n^2) > O(n)不满足

• HashMap的containsKey方法

//获取HashMap里面的节点数组是否为空
public boolean containsKey(Object key) {
   return getNode(hash(key), key) != null;
}

//1)数组不为空
//2)数组长度>0
//3)通过hash计算出该元素在数组中存放位置的索引,而且该索引处数据不为空null
final HashMap.Node<K,V> getNode(int hash, Object key) {
    HashMap.Node<K,V>[] tab; HashMap.Node<K,V> first, e; int n; K k;
    if ((tab = table) != null && (n = tab.length) > 0 &&
            (first = tab[(n - 1) & hash]) != null) {
        //判断该数组索引位置处第一个是否为我们要找的元素 判断条件需要满足hash 和 key 相同
        if (first.hash == hash && // always check first node
                ((k = first.key) == key || (key != null && key.equals(k))))
            //如果第一个就是我们要找的,直接返回即可
            return first;
        //如果第一个不是,我们需要循环遍历,然后找数据
        if ((e = first.next) != null) {
            //如果第1个的元素是红黑树类型的节点
            if (first instanceof HashMap.TreeNode)
                //那我们需要调用红黑树的方法查找节点
                return ((HashMap.TreeNode<K,V>)first).getTreeNode(hash, key);
            //如果不是,则该为链表,需要遍历查找
            do {
                //循环判断下一个节点的hash和key是否相同
                if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    //没找到返回Null
    return null;
}

可以看出要么第一个索引直接命中时间复杂度为O(1)，如果没有命中则遍历红黑树的节点，遍历红黑树的节点时间复杂度为O(lgn)，也就是说时间复杂度最大是O(lgn)最小是O(1)，都比O(n)要小，所以这个是能满足条件。关于HashMap的containsKey的时间复杂度的解释可以参考这篇文章

• 围绕HashMap的ContainsKey方法，思考代码编写思路：
  1. 单个数组去重放入新的容器
  2. 拿新的容器对比另一个数组找出相同的元素
  3. 得到的所有相同的元素就是交集部分

private static void method2(int[] array1 ,int[] array2){
    long start = System.currentTimeMillis();
    HashMap<Integer,Boolean> map = new HashMap<>();
    //单个数组去重，放入新的容器，并且给每一个元素打上一个boolean标记false。
    for (int array1Element :array1 ) {
        if (!map.containsKey(array1Element)) {
            map.put(array1Element,false);
        }
     }
     //拿上新的容器去跟另一个数组比较,如果新的容器里面有相同的Key,就说明是交集元素，打上另一个boolean标记true。
     for (int array2Element :array2 ) {
        if (map.containsKey(array2Element)) {
            map.put(array2Element,true);
        }
      } 
      StringBuffer sb = new StringBuffer();
      //遍历新的容器，找出boolean标记为true所对应的键，就是交集元素了
      for (Map.Entry<Integer,Boolean> e : map.entrySet() ) {
        if (e.getValue().equals(true)) {
            sb.append(e.getKey()+",");
        }    
      }
      long end = System.currentTimeMillis();
      System.out.println("method2 两个数组的交集为：" + sb.toString() + "耗时 = " + (end - start)+ "ms");
}

测试结果：100个10以内的数字，方法耗时1ms，1000个10以内的数字耗时2ms，10000个10以内的数耗时5ms

大家如果还有更优算法，欢迎下方欢迎留言，大家一起探讨～～