共计 1789 个字符，预计需要花费 5 分钟才能阅读完成。
350. 两个数组的交加 II
题目起源：力扣（LeetCode）https://leetcode-cn.com/problems/intersection-of-two-arrays-ii
题目
给定两个数组，编写一个函数来计算它们的交加。
示例 1:
输出: nums1 = [1,2,2,1], nums2 = [2,2]
输入: [2,2]示例 2:
输出: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输入: [4,9]阐明：
- 输入后果中每个元素呈现的次数，应与元素在两个数组中呈现的次数统一。
- 咱们能够不思考输入后果的程序。
进阶:
- 如果给定的数组曾经排好序呢？你将如何优化你的算法？
- 如果 nums1 的大小比 nums2 小很多，哪种办法更优？
- 如果 nums2 的元素存储在磁盘上，磁盘内存是无限的，并且你不能一次加载所有的元素到内存中，你该怎么办？
解题思路
思路：哈希表，双指针
先看题目，联合示例 1 和第一条阐明【输入后果中每个元素呈现的次数，应与元素在两个数组中呈现的次数统一】，由此咱们晓得，同一个数字在两个数组中，都有可能呈现屡次。
哈希表
在这里，咱们先说哈希表的思路。咱们能够应用哈希表来存储每个数字呈现的次数。在这里，咱们要求两个数组的交加，那么这里数字呈现的次数取决于两个数组中呈现次数较小的局部。
在这里，咱们能够思考对较短的数组进行遍历，在哈希表中记录数字以及对应呈现的次数。而后再遍历另外一个数组，如果数字存在于哈希表中，那么将数字增加到后果列表中，而后将哈希表对应数字的次数减 1。（这里抉择对较短数组进行遍历存哈希表，思考的是升高空间复杂度。）
对于哈希表思路的图解如下（示例 2）：
具体实现代码见【代码实现 # 哈希表】
双指针
在题目前面的进阶当中 第一个问题，提到如果数组都是曾经排好序的，该如何优化算法？
在这里，咱们能够思考应用双指针的办法。双指针思路的算法大抵如下：
- 首先定义双指针，别离指向两个数组的首元素。
-
开始比拟双指针指向的元素，对以下的状况进行解决：
- 如果两个元素不相等，指针指向元素较小的向后挪动；
- 如果两个元素相等，则将元素增加到后果列表中，而后两个指针同时向后挪动。
- 当任意指针达到开端时，完结遍历。
对于双指针思路的图解如下（示例 2）：
具体实现代码见【代码实现 # 双指针】
在这里，针对进阶的 第三个问题 大抵的阐明下。如果呈现 nums2 的元素存储在磁盘上，磁盘内存无限，无奈一次加载所有的元素到内存中。那么此时想要疾速进行排序，则不太可能，所以倡议应用哈希表的思路。针对哈希表的思路，数组波及的是查问操作，能够思考读取局部信息进行解决。
代码实现
# 哈希表
class Solution:
def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
# 针对较短数组进行遍历将元素存于哈希表中
# 保障后面的数组较短
if len(nums1) > len(nums2):
self.intersect(nums2, nums1)
hash_map = {}
for num in nums1:
if num not in hash_map:
hash_map[num] = 0
hash_map[num] += 1
ans = []
for num in nums2:
# 查看是否存在于哈希表中
count = hash_map.get(num, 0)
# 元素存在于哈希表中，则增加入后果列表中
# 而后将哈希表对应的元素呈现次数减一
if count > 0:
ans.append(num)
hash_map[num]-=1
return ans
# 双指针
class Solution:
def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
nums1.sort()
nums2.sort()
p = q = 0
ans = []
# 任意指针达到数组开端，完结遍历
while p < len(nums1) and q < len(nums2):
# 在这里，先判断指针对应元素的大小
# 当不相等时，指针对应元素小的挪动
# 相等时，将元素放入后果列表中，同时挪动指针
if nums1[p] > nums2[q]:
q+=1
elif nums1[p] < nums2[q]:
p += 1
else:
ans.append(nums1[p])
p += 1
q += 1
return ans
实现后果
哈希表 | 实现后果
双指针 | 实现后果
欢送关注
公众号【书所集录】
