4.两个数组的交集Ⅱ

题目描述

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

示例 1：
输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2,2]
链接：https://leetcode-cn.com/problems/intersection-of-two-arrays-ii

方法1、暴力解法

思路：遍历nums1，判断各数是否存在于nums2，存在，存入结果，并把该数从nums2划掉；不存在，继续判断下一个数。

注意：从这个思路可以隐约感受到为什么哈希表法需要-1。

执行时间：60ms

时间复杂度：O(mn)

class Solution:
    def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
        # 暴力解法
        r=list()
        for i in nums1:
            if i in nums2:
                r.append(i)
                nums2.remove(i)
        return r

方法2、哈希表

思路总结：

1、排序，先处理更短的list；
2、new一个哈希表，存放数组1各数字出现的次数；（collections.Counter()即可实现）
3、遍历数组2，如果哈希表存在该数，取出为输出结果；并且哈希表该数出现次数-1；如果出现次数=0了（没得减了），就pop掉该数。

为什么减1，我的理解是第一个数组遍历完，最多出现次数只能和数组1一致，多了也没用了

注意：:= 海象运算符。

执行用时：36 ms

时间复杂度：O(m+n)，m,n为两数组的长度，需遍历两数组并操作哈希表。哈希表操作时间复杂度为O(1)

空间复杂度：O(min(m,n))，哈希表不超过较短的list，返回结果的list也不超过较短的list。

class Solution:
    def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
        # 哈希表
        if len(nums1)>len(nums2):
            return self.intersect(nums2, nums1)
        r = list()
        d = collections.Counter()  
        # 也可以直接用d = collections.Counter(nums1)
        for num in nums1:
            d[num]+=1
        for i in nums2:
            if (count := d.get(i,0)) >0:
                r.append(i)
                d[i] -= 1
                if d[i]==0:
                    d.pop(i)
        return r

方法3、排序+双指针

思路：

1、两数组先排序。
2、设置两个指针分别对应两数组的头。
3、从左往后依次判断是否相等，不相等，较小的那个数组指针+1。
4、直到某一数组溢出，停止。

执行时间：40ms

时间复杂度：O(mlogm+nlogn)，排序需要O(mlogm+nlogn)，遍历两个数组需要O(m+n)。

空间复杂度：O(min(m,n))，返回结果的数组不超过较短的数组。

注意：推荐方法2，因为方法2的nums2只需查询操作，读取部分数据即可。

磁盘空间有限，而方法3排序需要加载nums2所有元素到内存中。

class Solution:
    def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
        # 排序+双指针
        nums1.sort()
        nums2.sort()
        len1, len2 = len(nums1), len(nums2)
        r = list()
        idx1=idx2=0
        while idx1<len1 and idx2<len2:
            if nums1[idx1] < nums2[idx2]:
                idx1 += 1
            elif nums1[idx1] > nums2[idx2]:
                idx2 += 1
            else:
                r.append(nums1[idx1])
                idx1 += 1
                idx2 += 1
        return r