找出两个数组的交集

交集是集合里的概念，而集合是不允许有重复元素的，然而数组却是允许重复元素的。
所以解这道题时要注意去重。

使用HashSet

这无疑是最简单，最取巧的方法。通过把一个数组放入HashSet中，然后再遍历第二个数组看元素是否存在于HashSet里即可找出交集，时间复杂度为 O(n) + O(m), n和m为两个数组的长度

    //使用HashSet
    public static Integer[] find2(int[] arr1, int[] arr2) {
        Set<Integer> resultSet = new HashSet<Integer>();
        
        //HashSet存取的时间复杂度都为O(1) 
        Set<Integer> set = new HashSet<Integer>();
        for(int num : arr1){
            set.add(num);
        }
        for(int num : arr2){
            if(set.contains(num)){
                resultSet.add(num);
            }
        }
        
        return resultSet.toArray(new Integer[resultSet.size()]);
    }

放入一个数组，排序，找相邻是否相同

1. 把两个数组分别去重后，放入一个数组， O(m+n)
2. 排序 O((m+n) * log2(m+n))
3. 遍历，相邻元素相同即为交集元素 O(m+n)

    //合并成一个数组，排序后遍历，相邻相同即为交集元素
    public static Integer[] find3(int[] arr1, int[] arr2) {
        Set<Integer> resultSet = new HashSet<Integer>();
        
        //给两个数组去重，合并
        Set<Integer> set1 = new HashSet<Integer>();
        for(int num : arr1){
            set1.add(num);
        }
        Set<Integer> set2 = new HashSet<Integer>();
        for(int num : arr2){
            set2.add(num);
        }
        List<Integer> list = new ArrayList<Integer>();
        list.addAll(set1);
        list.addAll(set2);
        Integer[] newArr = list.toArray(new Integer[list.size()]);
        
        //排序
        Arrays.sort(newArr);
        
        //遍历一遍,相邻相同即是交集
        Integer previous = null;
        for(Integer current : newArr){
            if(previous == current){
                resultSet.add(previous);
            }
            previous = current;
        }
        
        return resultSet.toArray(new Integer[resultSet.size()]);
    }

分别排序，交叉查找

1. 分别排序, O(n*log2n) + O(m*log2m)
2. 交叉查找, O(n+m)

    //对两个数组排序，然后交叉查找
    public static Integer[] find1(int[] arr1, int[] arr2) {
        //排序
        Arrays.sort(arr1);
        Arrays.sort(arr2);
        
        Set<Integer> resultSet = new HashSet<Integer>();

        int indexOfArr1 = 0;
        int indexOfArr2 = 0;
        while (indexOfArr1 < arr1.length && indexOfArr2 < arr2.length) {
            //从数组1中取出一个元素，逐一和数组2的元素比较，直到数组2的元素大于这个取出的元素
            int benchMarkInArr1 = arr1[indexOfArr1];
            for ( ; indexOfArr2 < arr2.length; indexOfArr2++) {
                if(benchMarkInArr1 == arr2[indexOfArr2]){
                    resultSet.add(benchMarkInArr1);
                }else if(benchMarkInArr1 < arr2[indexOfArr2]){
                    break;
                }
            }
            //数组1坐标后移一位
            indexOfArr1 = indexOfArr1 + 1;
            if(indexOfArr1 >= arr1.length || indexOfArr2 >= arr2.length){
                //任意数组已经遍历到头，那不再可能有更多的交集元素
                break;
            }
            //从数组2中取出一个元素，逐一和数组1的元素比较，直到数组1的元素大于这个取出的元素
            int benchMarkInArr2 = arr2[indexOfArr2];
            for ( ; indexOfArr1 < arr1.length; indexOfArr1++) {
                if(benchMarkInArr2 == arr1[indexOfArr1]){
                    resultSet.add(benchMarkInArr2);
                }else if(benchMarkInArr2 < arr1[indexOfArr1]){
                    break;
                }
            }
        }

        return resultSet.toArray(new Integer[resultSet.size()]);
    }

比起上一种解法，O(n*log2n) + O(m*log2m) 应该小于 O((m+n) * log2(m+n))，所以时间复杂度会低一些

代码

Code