问题

给定两个数组，求两个数组的交集，并以数组形式输出。

思路

1）先排序再比较：先对两个数组进行排序，遍历两个数组中的值并比较，如果相同，则将该值放入集合中。如果不同，则较小值的下标自增并继续比较.
2）通过map进行记录：key为集合中的具体值，value为该值在集合中出现的次数。 先遍历nums1，并将值添加到map中，接着遍历nums2， 判断遍历得到的nums2中的每一个值是否在map中，如果在map中则添加到集合中。

实现

1）先排序再比较

public class InterSect {

    public static void main(String[] args) {

        int[] nums1 = new int[]{4,9,5};
        int[] nums2 = new int[]{9,4,9,8,4};

        int[] result = interSect(nums1,nums2);

        System.out.println(Arrays.toString(result));
    }

    private static int[] interSect(int[] nums1, int[] nums2) {

        /**
         * 对数组排序
         * 对两个数组中的值进行逐一比较，相同放入集合，
         * 如果nums1[i]<nums2[j] ->i++
         * 如果nums1[i]>nums2[j] ->j++
         */
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        int i = 0;
        int j = 0;
        List<Integer> list = new ArrayList<>();

        while (i<nums1.length && j<nums2.length){

            if (nums1[i] == nums2[j]){
                list.add(nums1[i]);
                i++;
                j++;
            }else if (nums1[i]<nums2[j]){
                i++;
            }else if (nums2[j]<nums1[i]){
                j++;
            }
        }

        return list.stream().mapToInt(Integer::intValue).toArray();

    }
}

image.png

2）通过map记录

private static int[] interSect2(int[] nums1, int[] nums2) {
        //key 值  value 出现的次数
        Map<Integer,Integer> map = new HashMap<>();
        List<Integer> list = new ArrayList<>();

        //遍历nums1
        for (int i=0;i<nums1.length;i++) {
            map.put(nums1[i],map.getOrDefault(nums1[i],0)+1);
        }

        //遍历nums2
        for (int i=0;i<nums2.length;i++) {
            if (map.getOrDefault(nums2[i],0)>0){
                list.add(nums2[i]);
                map.put(nums2[i],map.getOrDefault(nums2[i],0)-1);
            }
        }

        return list.stream().mapToInt(Integer::intValue).toArray();
    }