requirements

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

Example 1:

Input: nums1 = [1,2,2,1], nums2 = [2,2] output: [2,2]Copy the code

Example 2:

Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4]Copy the code

Description:

  • The number of occurrences of each element in the output should be the same as the minimum number of occurrences of the element in both arrays.
  • We can ignore the order of the output.

Advanced:

  • What if the given array is already sorted? How will you optimize your algorithm?
  • If nums1 is much smaller than NUMs2, which method is better?
  • What do you do if nums2 elements are stored on disk, memory is limited, and you can’t load all elements into memory at once?

The core code

class Solution:
    def intersect(self, nums1: List[int], nums2: List[int]) - >List[int] :
        if len(nums1) > len(nums2):
            nums1,nums2 = nums2,nums1
        res = []
        for i in nums1:
            if i in nums2:
                res.append(i)
                nums2.remove(i)
        return res
Copy the code

Another solution

class Solution:
    def intersect(self, nums1: List[int], nums2: List[int]) - >List[int] :
        res_dict = {}
        res = []
        for i in nums1:
            if i in res_dict:
                res_dict[i] += 1
            else:
                res_dict[i] = 1
        for j in nums2:
            if j not in res_dict:
                continue
            else:
                if res_dict[j] == 0:
                    continue
                else:
                    res.append(j)
                    res_dict[j] -= 1
        return res
Copy the code

In the first solution, we use the remove method to remove the corresponding elements from the second list. Second solution: we use hash table to solve this problem, we first count the characters in a list and the number of characters, and finally can scan the second list, and finally get the intersection.