[daily question] intersection of two arrays

349. Intersection of two arrays

The difficulty is simple 227

Given two arrays, write a function to calculate their intersection.

Example 1:

输入：nums1 = [1,2,1],nums2 = [2,2]
输出：[2]

Example 2:

输入：nums1 = [4,9,5],nums2 = [9,4,8,4]
输出：[9,4]

explain:

reflection

1、 Solve using set

    public int[] intersection(int[] nums1,int[] nums2) {
        Set<Integer> set = new HashSet<>();
        Set<Integer> res = new HashSet<>();
        for(int num : nums1) set.add(num); //[1,1] -> [1,2]
        for(int num : nums2){
            if(set.contains(num))  res.add(num);//[2]
        }
        int[]arr = new int[res.size()];
        int index = 0;
        for(int num : res) arr[index++] = num;
        return arr;
    }

Time complexity: \ (O (M + n) \), the efficiency of HashSet in judging the existence of an element is O (1). Building a collection requires the length of one array, m, and traversing the other requires n.

Space complexity: \ (O (M + n) \), which requires a space of two set lengths.

2、 Use sort + double pointer

public int[] intersection(int[] nums1,int[] nums2) {
    Arrays.sort(nums1);
    Arrays.sort(nums2);
    Set<Integer> res = new HashSet<>();
    int i = 0,j = 0;
    while(i < nums1.length && j < nums2.length){
        if(nums1[i] == nums2[j]){
            res.add(nums1[i]);
            i++;j++;
        }else if(nums1[i] < nums2[j]){
            i++;
        }else{
            j++;
        }
    }
    int[] arr = new int[res.size()];
    int index = 0;
    for(int num : res) arr[index++]  = num;
    return arr;
}

Time complexity: \ (O (2nlogn + max (n, m)) \), the time complexity of sorting is \ (nlogn \), double pointer n.

Space complexity: \ (O (n) \)

350. Intersection of two arrays II

Given two arrays, write a function to calculate their intersection.

Example 1:

输入：nums1 = [1,2]
输出：[2,2]

Example 2:

输入：nums1 = [4,4]
输出：[4,9]

explain:

Advanced:

reflection

1、 Sort + double pointer

In fact, in the case of sorting, you can directly change set to list.

2、 Hash count

reference resources: https://leetcode-cn.com/problems/intersection-of-two-arrays-ii/solution/liang-ge-shu-zu-de-jiao-ji-ii-by-leetcode-solution/

    public int[] intersect(int[] nums1,int[] nums2) {

        if (nums1.length > nums2.length) {
            return intersect(nums2,nums1);
        }
        Map<Integer,Integer> map = new HashMap<Integer,Integer>();
        for (int num : nums1) {
            map.put(num,map.getOrDefault(num,0) + 1);
        }
        int[] res = new int[nums1.length];
        int index = 0;
        for (int num : nums2) {
            int count = map.getOrDefault(num,0);
            if (count > 0) {
                res[index++] = num;
                count--;
                if (count > 0) {
                    map.put(num,count);
                } else {
                    map.remove(num);
                }
            }
        }
        return Arrays.copyOfRange(res,index);
    }

Time complexity: \ (O (M + n) \), where m and N are the lengths of the two arrays respectively. It is necessary to traverse two arrays and operate the hash table. The time complexity of hash table operation is \ (O (1) \), so the total time complexity is linear with the sum of the lengths of the two arrays.

Spatial complexity: \ (O (min (m, n)) \), where m and N are the lengths of two arrays respectively. Perform hash table operation on a shorter array. The size of the hash table will not exceed the length of the shorter array. Create an array res for the return value, whose length is the length of the shorter array.