LeetCode 349. Intersection of two arrays (simple, array) Day12

Title Description ： Given two arrays nums1 and nums2 , return Their intersection . Every element in the output must be only Of . We can Regardless of the order of the output results .

Example 1：

 Input ：nums1 = [1,2,2,1], nums2 = [2,2]
 Output ：[2]

Example 2：

 Input ：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
 Output ：[9,4]
 explain ：[4,9]  It is also passable 

Tips ：
1 <= nums1.length, nums2.length <= 1000
0 <= nums1[i], nums2[i] <= 1000

Conclusion ideas ：

Method 1 ： Sort + Double pointer

1、 Let me declare one List aggregate , Used to store the same elements in two arrays , The reason for not using arrays is that the array length is fixed , I don't know how many elements are the same , So it's best to use collections ;
2、 First sort the two sets ;
3、 Traverse two arrays to find the same element , Add the same elements to the collection , But before adding to the collection, you must judge whether the element already exists in the collection , If it already exists, discard the addition ;
4、 Add elements from the collection to the array , Return the array .

Method 2 ： Use HashSet aggregate

1、 Declare two Set aggregate ,set1, set2（Set The basic characteristic of a set is disorder , No index , Do not repeat ）;
2、 Put the array nums1 Add elements from to set1 Collection ;
3、 Traversal array nums2, Judge nums2 Whether the elements in set1 Exists in collection , If present, add to set2 Collection , Otherwise, discard the element , Until the end of the traversal ;
4、 hold set2 The elements in the collection can be copied into the array , Last return array .

If you want to know more about Collection In a collection system Set and List aggregate , You can refer to the article ：https://blog.csdn.net/qq_43751200/article/details/123803851

Code implementation ：

public class Intersection {
    public static void main(String[] args) {
        int[] nums1 = {4,9,5};
        int[] nums2 = {9,4,9,8,4};
        System.out.println(Arrays.toString(intersection1(nums1, nums2)));
    }

    //  Method 1：  Sort  +  Double pointer 
    public static int[] intersection(int[] nums1, int[] nums2) {
        // 1.  Make a statement List aggregate 
        List<Integer> list = new ArrayList<>();

        // 2.  An array nums1, nums2 Sort 
        Arrays.sort(nums1);
        Arrays.sort(nums2);

        // 3.  Traverse the array to find the same element 
        int m = 0, n = 0;
        while (m < nums1.length && n < nums2.length){
            if(nums1[m] == nums2[n]){
                if(list.contains(nums1[m])){
                    //  If it already exists in the collection , There's nothing to do 
                }else {
                    list.add(nums1[m]);
                }
                //  The pointer needs to move forward 
                m++;
                n++;
            }else if(nums1[m] > nums2[n]){
                n++;
            }else {
                m++;
            }
        }

        // 4.  hold list Convert array to array 
        int[] nums = new int[list.size()];
        for(int i = 0; i < nums.length; i++){
            nums[i] = list.get(i);
        }

        return nums;
    }

    //  Method 2：Set aggregate 
    public static int[] intersection1(int[] nums1, int[] nums2) {
        Set<Integer> set1 = new HashSet<>();    // HashSet characteristic ： disorder 、 No repetition 、 No index .
        Set<Integer> set2 = new HashSet<>();

        for(int i = 0; i < nums1.length; i++){
            set1.add(nums1[i]);
        }

        for(int i = 0; i < nums2.length; i++){
            if(set1.contains(nums2[i])){
                set2.add(nums2[i]);
            }
        }

        int[] nums = new int[set2.size()];
        int k = 0;
        for(Integer it : set2){
            nums[k++] = it;
        }
        return nums;
    }
}

source ： Power button （LeetCode）
link ：https://leetcode-cn.com/problems/intersection-of-two-arrays