题目

难度：★★☆☆☆
类型：数组

给定两个数组，编写一个函数来计算它们的交集。

说明：
输出结果中每个元素出现的次数，应与元素在两个数组中出现的次数一致。
我们可以不考虑输出结果的顺序。

进阶:
如果给定的数组已经排好序呢？你将如何优化你的算法？
如果 nums1 的大小比 nums2 小很多，哪种方法更优？
如果 nums2 的元素存储在磁盘上，磁盘内存是有限的，并且你不能一次加载所有的元素到内存中，你该怎么办？

示例

示例 1:
输入: nums1 = [1,2,2,1], nums2 = [2,2]
输出: [2,2]

示例 2:
输入: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出: [4,9]

解答

这道题与【题目349. 两个数的交集】唯一的不同，就是结果中数值相同的元素可以重复出现。

方案1：交集定义

我们可以遍历其中一个数组，如果当前数字在另一个数组中出现，则记录下当前结果的同时，删除另一个数组中的该元素，遍历完成即可实现题目所描述的求取交集的任务。

class Solution(object):
    def intersect(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: List[int]
        """
        r = []                      # 结果列表
        tmp = nums2[:]              # 准备一个临时变量，复制nums2，为了防止对nums2的修改
        for num in nums1:           # 遍历nums1中的每一个变量num
            if num in tmp:          # 如果当前元素num在另一个数组中出现过

                r.append(num)       # 则把该元素添加到结果中
                tmp.remove(num)     # 并且删除另一个数组中的这条记录
        return r                    # 返回结果列表

方案2：双指针

我们首先对两个数组进行排序，然后分别用两个指针从头开始遍历，如果遇到相同元素则记录结果，如果不相等，则把数值较小的元素所在的指针向右移动。

class Solution(object):
    def intersect(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: List[int]
        """
        res = []                                    # 结果列表
        nums1.sort()                                # 排序数组1
        nums2.sort()                                # 排序数组2
        i = j = 0                                   # 初始化两个遍历指针
        while i < len(nums1) and j < len(nums2):    # 当指针位置合法时
            if nums1[i] < nums2[j]:                 # 比较当前各个指针所指元素大小关系
                i += 1                              # 如果不相等，则根据大小关系移动指针
            elif nums1[i] > nums2[j]:
                j += 1
            else:                                   # 如果相等
                res.append(nums1[i])                # 加入结果列表
                i += 1                              # 移动两个指针
                j += 1

        return res

如有疑问或建议，欢迎评论区留言~