查找两个数组中的相同数

题目：查找两个数组中的相同数

方案一：

最笨的办法莫过于双重循环了，这种我们并不考虑，因为时间复杂度是N*N；

方案二：

如果只用数组的话，可以采用先排序，然后再用两个指针顺序找，只需要一次循环就可以。

public static Set<Integer> findCommon(int[] arr1, int[] arr2) {
        Set<Integer> set= new HashSet<>();
        if (arr1 == null || arr2 == null || arr1.length == 0 || arr2.length == 0) {
            return set;
        }
        Arrays.sort(arr1);
        Arrays.sort(arr2);
        int i = 0, j = 0;
                //循环完成任何一个数组就结束
        while ( i < arr1.length && j < arr2.length ) {
                        //这种算法会导致有重复值，所以才需要用到HashSet去重
            if(arr1[i] == arr2[j]){
                set.add(arr1[i]);
                i++;
                j++;
                continue;
            }
            if(arr1[i] < arr2[j]){
                i++;
            }else {
                j++;
            }
        }
        return list;
    }

    public static void main(String[] args) {
        int a[] = {1,1,1,1,3,5,6,8,9};
        int b[] = {1,1,3,5,7,10,12};

        Set<Integer> result = findCommon(b,a);
        for (int i : result){
            System.out.print(i+",");
        }
    }

方案三：

采用HashMap，key为数组中值，value>1的为重复值。
需要先去重，然后循环一次就可以。

public static Set<Integer> findCommon2(Integer[] arr1, Integer[] arr2){
        Set<Integer> list = new HashSet<>();
        if (arr1 == null || arr2 == null || arr1.length == 0 || arr2.length == 0) {
            return list;
        }
        String[] strArray= new String[]{"Tom", "Bob", "Jane"};


        Set<Integer> set1 = new HashSet<>(Arrays.asList(arr1));
        Set<Integer> set2 = new HashSet(Arrays.asList(arr2));
        Map<Integer,Integer> map = new HashMap<>();


        Iterator<Integer> its1 = set1.iterator();
        Iterator<Integer> its2 = set2.iterator();
        int key1 = 0;Integer key2 = 0;
        while( its1.hasNext() || its2.hasNext()){
            if(its1.hasNext() && its2.hasNext()){
                key1 = its1.next();
                key2 = its2.next();
                map.put(key1, map.get(key1)==null?1:map.get(key1)+1);
                map.put(key2, map.get(key2)==null?1:map.get(key2)+1);
            }else if (its1.hasNext() ) {
                key1 = its1.next();
                map.put(key1, map.get(key1)==null?1:map.get(key1)+1);
            } else if (its2.hasNext()) {
                key2 = its2.next();
                map.put(key2, map.get(key2)==null?1:map.get(key2)+1);
            }
        }


        Set<Integer> keys = map.keySet();
        Iterator<Integer> its = keys.iterator();
        while (its.hasNext()){
            Integer key = its.next();
            if(map.get(key)>1){
                list.add(key);
            }
        }
        return list;
    }

    public static void main(String[] args) {
        Integer a[] = {1,1,1,1,3,5,6,8,9};
        Integer b[] = {1,1,3,5,7,10,12};

        Set<Integer> result = findCommon2(b,a);
        for (int i : result){
            System.out.print(i+",");
        }
    }