题目

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

示例 1:

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

示例 2:

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

说明：

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

进阶:

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

题解

思路

  • 建立一个哈希表，键为nums1的数，值为这个数出现的次数
  • 遍历num2,当num2的数出现在哈希表中，将它添加到答案里，同时更新哈希表，让其出现次数减一。

代码

1
2
3
4
5
6
7
8
9
10
from collections import defaultdict
class Solution:
    def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
        dic, ans = defaultdict(int), list()
        for i in nums1: dic[i] += 1
        for i in nums2:
            if dic[i] != 0:
                ans.append(i)
                dic[i] -= 1
        return ans
  • defaultdict(int)项对第一次出现的键会初始化一个0的值
  • 这题也可以使用Counter直接统计出字符出现的次数，和手动遍历是一样的。

复杂度分析

假设num1有M项，num2有m项，其中M>m，则

  • 时间复杂度 O(M+m)O(M+m)
  • 空间复杂度 O(m)O(m)