350. Intersection of Two Arrays II

# Easy

Two methods: (assume len(nums1) < len(nums2))

1. 暴力解法. Ask each element in nums1 whether in nums2, if yes, then remove this element from both lists and add to result list.

2. Hash map. Build a dictinonary <numss[i], n>, means nums1[i] appears n times in nums1. Use this dictionary to traversal all elements in nums2.

Python(I)

Time complexity = $O(min(n, m))$if if x in nums2 only consume $O(1)$ ; space complexity = $O(min(n, m))$

class Solution:
    def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
        if len(nums1) < len(nums2):
            return self.helper(nums1, nums2)
        else:
            return self.helper(nums2, nums1)
        
    def helper(self, nums1, nums2):
        result = []
        while len(nums1) != 0:
            x = nums1.pop()
            if x in nums2:
                result.append(x)
                nums2.remove(x)
            
        return result

Second Tab

Time complexity = $O(m+n)$, if if x in dic only consume $O(1)$ ; space complexity = $O(m+n)$

class Solution:
    def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
        if len(nums1) < len(nums2):
            return self.helper(nums1, nums2)
        else:
            return self.helper(nums2, nums1)
        
    def helper(self, nums1, nums2):
        dic = {}
        result = []
        
        for x in nums1:
            if x in dic:
                dic[x] = dic[x] + 1
            else:
                dic[x] = 1

        for x in nums2:
            print(x)
            if x in dic and dic[x] > 0:
                dic[x] = dic[x] - 1
                result.append(x)
                
        return result