Given two arrays, write a function to calculate their intersection

Example 1:

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

Example 2:

Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
Output: [4,9]

explain:

• The number of occurrences of each element in the output result shall be consistent with the minimum number of occurrences of elements in the two arrays.
• We can ignore the order of output results.

==map mapping

=================================Python===============================

class Solution:
    def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
        dic1 = {}
        dic2 = {}
        for val in nums1:
            if val in dic1:
                dic1[val] += 1
            else:
                dic1[val] = 1
        for val2 in nums2:
            if val2 in dic2:
                dic2[val2] += 1
            else:
                dic2[val2] = 1
        res = []
        for key, value in dic1.items():
            if key in dic2:
                for _ in range(min(dic2[key], value)):
                    res.append(key)
        return res
----------------------------optimization------------------------------

class Solution:     def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:         dic = {}         for val in nums1:             if val in dic:                 dic[val] += 1             else:                 dic[val] = 1         k = 0         for value in nums2:             if dic.get(value, 0) > 0:                 dic[value] -= 1                 nums2[k] = value                 k += 1         return nums2[:k]

========================================Go======================================

func intersect(nums1 []int, nums2 []int) []int {
    m0 := map[int]int{}
    for _, v := range nums1 {
        m0[v] += 1
    }
    k := 0
    for _, v := range nums2 {
        if m0[v] > 0 {
            m0[v] -= 1
            nums2[k] = v
            k++
        }
    }
    return nums2[0:k]
}

=====================================Java=================================

class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        HashMap<Integer, Integer> map1 = new HashMap<>();
        for (int num: nums1){
            int count = map1.getOrDefault(num, 0) + 1;
            map1.put(num, count);
        }

        int[] res = new int[nums1.length]; 
        int index = 0;
        for (int num: nums2){
            int count = map1.getOrDefault(num, 0);
            if (count > 0) {
                count--;
                res[index++] = num;
                if (count > 0) {
                    map1.put(num, count);
                } else {
                    map1.remove(num);
                }
            }
        }

        return Arrays.copyOfRange(res, 0, index);
    }
}

Advanced:

What if the given array is already ordered? How will you optimize your algorithm?
If the size of ， nums1 ， is much smaller than ， nums2 ， which method is better?

If the elements of "nums2" are stored on disk, the disk memory is limited, and you can't load all the elements into memory at one time, what should you do?

Corresponding to advanced problem 3, if the memory is too small to load all the arrays into memory, the space consuming algorithms such as hash must not be used, and only the algorithm with the least space complexity can be selected.

Generally speaking, sorting algorithms are aimed at internal sorting. Once dealing with disk (external sorting) is involved, special considerations are required. Merge sorting is a natural algorithm suitable for external sorting. You can write the divided sub array to a single file, and merge small files into larger files. When both arrays are sorted to generate two large files, you can use double pointers to traverse the two files, which can minimize the space complexity.

Double pointer

===============Python=============

class Solution:
    def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
        nums1.sort()
        nums2.sort()
        i = j = 0
        res = []
        while i < len(nums1) and j < len(nums2):
            if nums1[i] == nums2[j]:
                res.append(nums1[i])
                i += 1
                j += 1
            elif nums1[i] < nums2[j]:
                i += 1
            else:
                j += 1
        return res

============Go==========

func intersect(nums1 []int, nums2 []int) []int {
    i, j, k := 0, 0, 0
    sort.Ints(nums1)
    sort.Ints(nums2)
    for i < len(nums1) && j < len(nums2) {
        if nums1[i] > nums2[j] {
            j++
        } else if nums1[i] < nums2[j] {
            i++
        } else {
            nums1[k] = nums1[i]
            i++
            j++
            k++ 
        }
    }
    return nums1[:k]
}

======================Java====================

class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
       Arrays.sort(nums1);
       Arrays.sort(nums2);
       int l1 = nums1.length;
       int l2 = nums2.length;
       int i = 0;
       int j = 0;
       int index = 0;
       while (i < l1 && j < l2) {
           if (nums1[i] == nums2[j]) {
               nums1[index++] = nums1[i];
               i ++;
               j ++;
           } else if (nums1[i] > nums2[j]) {
               j ++;
           } else {
               i ++;
           }
       }
       return Arrays.copyOfRange(nums1, 0, index);
}
}