350. 两个数组的交集 II, Intersection of Two Arrays II

题目

给你两个整数数组 nums1 和 nums2 ，请你以数组形式返回两数组的交集。返回结果中每个元素出现的次数，应与元素在两个数组中都出现的次数一致（如果出现次数不一致，则考虑取较小值）。可以不考虑输出结果的顺序。

Given two integer arrays nums1 and nums2, return an array of their intersection. Each element in the result must appear as many times as it shows in both arrays and you may return the result in any order.

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] Explanation: [9,4] is also accepted.

要点

input: nums1->list[int], nums2->list[int]
output: result->list[int]

我的代码

class Solution:
    def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:     
        result = []
        hashmap={}
        for i,value in enumerate (nums1):
            hashmap[i]=value
        for num in nums2:
            if num in hashmap.values():
                result.append(num)
                del_index = list(hashmap.values()).index(num)
                key = list(hashmap.keys())[del_index]                    
                del hashmap[key]
        return result

思路

nums1用hashmap表示，hashmap的key从0至n，value存nums1中的值。nums2遍历查找，找到了就删掉hashmap中对应的项。
缺点：没有很好地利用到key/value之间的规律，可以用key作为值，value作为一个counter，只要对应counter大于0，每次找到就count-1,并将值放入result中

counter方法

class Solution(object):
    def intersect(self, nums1, nums2):

        counts = {}
        res = []

        for num in nums1:
            counts[num] = counts.get(num, 0) + 1

        for num in nums2:
            if num in counts and counts[num] > 0:
                res.append(num)
                counts[num] -= 1
        return res

分析

很好地利用了key存值，value为counter。表现形式：{值：出现的次数}。 其中counts.get(num, 0) + 1的分析如下
dict.get(key, default=None)函数会返回key对应的value。如果key不存在，返回value。当不写value时，value默认为None。Line 8 相当于 counts[num] = value + 1，value默认值为0.

双指针方法

class Solution(object):
    def intersect(self, nums1, nums2):

        nums1, nums2 = sorted(nums1), sorted(nums2)
        pt1 = pt2 = 0
        res = []

        while True:
            try:
                if nums1[pt1] > nums2[pt2]:
                    pt2 += 1
                elif nums1[pt1] < nums2[pt2]:
                    pt1 += 1
                else:
                    res.append(nums1[pt1])
                    pt1 += 1
                    pt2 += 1
            except IndexError:
                break

        return res

分析

巧妙运用try catch避免了index out of bound的错误，一旦有一方用尽则会跳出while loop， 不过前提是sorted array

collections方法

class Solution(object):
    def intersect(self, nums1, nums2):

        counts = collections.Counter(nums1)
        res = []

        for num in nums2:
            if counts[num] > 0:
                res += num,
                counts[num] -= 1

        return res

分析

需要import collection，原理同counter方法。collections.Counter(nums1) 会生成dict并将nums1中的元素计数放入，{值：出现的次数}