编号349：两个数组的交集

编号349：两个数组的交集

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

「说明：」
输出结果中的每个元素一定是唯一的。
我们可以不考虑输出结果的顺序。

思路

注意题目特意说明：「输出结果中的每个元素一定是唯一的，也就是说输出的结果的去重的， 同时可以不考虑输出结果的顺序」

这道题用暴力的解法时间复杂度是O(n^2)，那来看看使用哈希法进一步优化。

可以发现，貌似用数组做哈希表可以解决这道题目，把nums1的元素，映射到哈希数组的下表上，然后在遍历nums2的时候，判断是否出现过就可以了。

但是要注意，「使用数据来做哈希的题目，都限制了数值的大小，例如哈希表：可以拿数组当哈希表来用，但哈希值不要太大题目中只有小写字母，或者数值大小在[0- 10000] 之内等等。」

而这道题目没有限制数值的大小，就无法使用数组来做哈希表了。

「而且如果哈希值比较少、特别分散、跨度非常大，使用数组就造成空间的极大浪费。」

代码

public class 三四九题两个数组的交集 {
    public static void main(String[] args) {
        int [] num1 = {1,2,2,1};
        int [] num2 = {2,2};
        int[] arraryIntersect = arraryIntersectSort(num1, num2);
        System.out.println(Arrays.toString(arraryIntersect));

    }
    //使用哈希法
    public static int [] arraryIntersect(int [] num1, int [] num2){
        HashMap<Integer,Integer> map = new HashMap<>();
        List<Integer> list = new ArrayList<>();
        for(int num : num1){
            if( !map.containsKey(num) ){
                map.put( num,1 );
            }else{
                map.put( num,map.get(num)+1 );
            }
        }

        for( int num : num2){
            if( map.containsKey( num )){
                map.put( num, map.get(num)-1);
                if( map.get(num) == 0 ){
                    map.remove( num );
                    list.add( num );
                }
            }
        }

        int res [] =new int [list.size()];

        for( int i = 0; i < list.size(); i++ ){
            res[i] = list.get(i);
        }

        return res;
    }

    //使用排序的方法利用双指针
    public static int [] arraryIntersectSort(int [] num1, int [] num2){
        List<Integer> list = new ArrayList<>();
        Arrays.sort( num1 );
        Arrays.sort( num2 );
        int p1 = 0;
        int p2 = 0;
        while( p1 < num1.length && p2 < num2.length ){
            if( num1[p1] == num2[p2]) {
            list.add( num1[p1] );
            p1++;
            p2++;
            }else if( num1[p1] < num2[p2] ){
                p1++;
            }else{
                p2++;
            }
        }
        int res [] =new int [list.size()];

        for( int i = 0; i < list.size(); i++ ){
            res[i] = list.get(i);
        }
        return res;
    }
}

---