Intersection of Two Arrays
你会得到两个整数数组，nums1 和 nums2。返回同时出现在两个数组中的所有值，并按升序排列。每个共有值在答案中只出现一次，无论它在任一数组中重复了多少次。
函数
- nums1integer-array
- 第一个整数列表
- nums2integer-array
- 第二个整数列表
- 返回值integer-array
- 两个列表中都出现的值，每个值只出现一次，并按升序排列
约束条件
1 ≤ nums1.length, nums2.length ≤ 5000-105 ≤ nums1[i], nums2[i] ≤ 105- 至少有一个值同时出现在两个数组中。
示例
- 输入
- nums1 = [6, 2, 9, 2, 4]nums2 = [4, 4, 1, 6]
- 输出
- [4, 6]
- 解释
4和6都在两个数组中。4在nums2中出现了两次，但只列出一次，而2和9从未出现在nums2中。
- 输入
- nums1 = [-3, 0, 7]nums2 = [7, -3, -3, 5]
- 输出
- [-3, 7]
- 解释
- 两个数组中都有
-3和7。按升序排列时，-3在前，尽管在nums2中7在前。
进阶
如果 nums1 有 10 个值，而 nums2 有一百万个值，并且已经排好序，你会选择哪种方法？二分查找能比完整遍历更快吗？
提示
逐个打开提示，每个都会多透露一点。
对于
nums1中的每个值，你都可以扫描整个nums2。每个数组有 5000 个值时，最多需要进行2.5 × 10^7次比较。你在反复询问什么问题？反复要问的问题是“这个值是否在另一个数组中？”。用一个数组构建的哈希集合，平均可以在常数时间内回答这个问题。
根据
nums1创建一个集合。遍历nums2；如果某个值在集合中，就把它添加到答案中，并从集合中移除，这样后续出现的副本就不会被再次添加。返回答案前先对其排序。
题解
每个共有值在答案中只出现一次，无论它重复多少次，而且答案必须经过排序。对两个数组进行排序后，两个指针就能按顺序找到共有值；而用其中一个数组构建哈希集合，可以在常数时间内回答“这个值是否在 nums1 中？”
比较每一对
结果正确，但无法在最大的测试中运行完毕
思路
对于 nums1 中的每个值，扫描 nums2，并在找到第一个匹配项时停止。跳过已经在答案中的值，因此 [8, 8, 8, 8] 与 [8, 8] 比较时只会得到一个 8，并在最后对答案排序。只要某个值的任意一个副本找到匹配项，就将该值加入答案；跳过操作可确保它只加入一次。每个值都可能需要扫描整个 nums2：如果每个数组中有 5000 个值，最多需要进行 2.5 × 10^7 次比较；而当匹配的值很少时，大多数扫描都会进行到末尾。
算法
- 先创建一个空的答案列表。
- 对于
nums1中的每个值a，如果它已经在答案中，就跳过它。 - 否则，扫描
nums2；遇到第一个等于a的值时，将a添加到答案中，然后停止扫描。 - 按升序排列答案并返回。
def intersection(nums1, nums2):
result = []
for a in nums1:
if a in result:
continue
# Look for a anywhere in nums2.
for b in nums2:
if a == b:
result.append(a)
break
result.sort()
return result先对两者排序，然后用两个指针遍历
思路
排序后，示例 1 变成 [2, 2, 4, 6, 9] 和 [1, 4, 4, 6]。移动较小值对应的指针：在另一个数组中，后面的每个值都至少和它一样大，因此它不可能再与后面的任何值匹配。相等的值是共有值，所以将该值加入答案，并移动两个指针。两边都重复出现的值，例如 [2, 2, 3] 和 [2, 2] 中的 2，会匹配两次；通过与最后加入的值比较，可以只保留一份。最终得到的答案是有序的。
排序的时间复杂度为 O(n log n + m log m)，遍历的时间复杂度为 O(n + m)，因为每一步都会移动一个指针。排序副本需要 O(n + m) 的内存；像 C 代码那样原地排序，只会额外保留答案。
算法
- 对两个数组进行排序。
- 设置
i = 0和j = 0。 - 当两个指针都在各自数组内时，移动指向较小值的指针。
- 值相等时，如果该值不等于上一个添加的值，就将其添加，然后移动两个指针。
- 返回答案。
def intersection(nums1, nums2):
a = sorted(nums1)
b = sorted(nums2)
i, j = 0, 0
result = []
while i < len(a) and j < len(b):
if a[i] < b[j]:
i += 1
elif a[i] > b[j]:
j += 1
else:
# A shared value: keep it once, even if it repeats.
if not result or result[-1] != a[i]:
result.append(a[i])
i += 1
j += 1
return result第一个数组的哈希集合
思路
将 nums1 中的每个值都放入哈希集合；在示例 1 中，重复的 2 会合并，只留下 {6, 2, 9, 4}。遍历 nums2，用常数时间查找每个值，并在匹配时立即将该值从集合中移除：第一个 4 会加入答案，第二个则找不到匹配项。每个加入答案的值都存在于两个数组中，而每个共有值都会在 nums2 中第一次出现时加入答案。
平均而言，遍历需要 O(n + m)。答案按 nums2 中的顺序排列，因此需要在 O(k log k) 时间内对其中的 k ≤ min(n, m) 个值排序。C 没有内置的集合，因此 C 代码使用以 value + 10^5 为索引的标记数组。
算法
- 根据
nums1构建哈希集合first。 - 对于
nums2中的每个值，如果它在first中，就将它添加到答案中，并从first中移除。 - 按升序对答案排序。
- 返回答案。
def intersection(nums1, nums2):
first = set(nums1)
result = []
for num in nums2:
if num in first:
result.append(num)
# Remove it so a repeat in nums2 is not added twice.
first.remove(num)
result.sort()
return result
易错点和边界情况
- 每次匹配时都添加一个值。
[2, 2, 3, 3, 3]和[3, 2, 2]会得到[2, 3]，而不是[3, 2, 2]。 - 按找到值的顺序返回。哈希集合的遍历顺序跟随
nums2，因此必须将[7, -3]排序为[-3, 7]。Python 的set(nums1) & set(nums2)也需要使用sorted。 - 把数字当作文本排序。JavaScript 不带比较器的
sort()会让[100000, 99]保持这个顺序。传入(x, y) => x - y。 - 用原始值作为标记数组的索引。
-3不是有效索引；将每个值都加上10^5。
常见问题3
两个数组的交集的时间复杂度是多少？
使用哈希集合查找共同值，平均需要 O(n + m)，另需 O(k log k) 对答案进行排序，并占用 O(n) 的空间。对两个数组排序后再遍历，需要 O(n log n + m log m)。比较每一对元素需要 O(n × m)。
你应该使用哈希集合还是双指针？
当数组未排序且有可用内存时，使用哈希集合：它所需的操作最少。当两个数组都已排序，或者内存紧张且你可以原地排序时，使用双指针。这种遍历不需要集合，并且会按顺序生成答案。
如何保留交集中的重复值？
当一个值应该按它在两个数组中出现的次数重复出现时，例如 [3, 1, 3, 3] 和 [3, 3] 得到 [3, 3]，就在映射中统计 nums1。对于 nums2 中计数大于 0 的每个值，将它添加进去并减少计数。双指针遍历只是不再检查最后添加的值。
相似题目
运用相同思路的题目。做两三道，才能真正掌握一种模式。
def intersection(nums1, nums2):
# 在这里编写代码测试 #1
测试 #2
参数
nums1 = [6, 2, 9, 2, 4] nums2 = [4, 4, 1, 6]
预期输出
[4, 6]