时间：2020-9-3
题目地址：https://leetcode-cn.com/problems/intersection-of-two-arrays-ii/
题目难度：Easy
题目描述：
给定两个数组，编写一个函数来计算它们的交集。
示例 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：用计数
349加的set过滤重复，这个加个次数判断
代码段1：通过
class Solution: def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]: if nums1 == [] or nums2 == []:return [] res = [] for i in nums1: if i in nums2 and res.count(i) < min(nums1.count(i), nums2.count(i)): res.append(i) return res总结：
至少现在简单题无压力，只能这么安慰自己了思路2：用哈希
代码段2：通过
class Solution: def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]: n1, n2 = collections.Counter(nums1), collections.Counter(nums2) res = [] for i in n1: temp = min(n1[i], n2[i]) while temp: res.append(i) temp -= 1 return res总结：
次数还是哈希好使进阶
问题1：
排序双指针 时间复杂度：O(max(nlogn, mlogm, n+m))，空间复杂度：O(1)，如果已排序O（n）即可
class Solution: def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]: nums1.sort() nums2.sort() res = [] left, right = 0, 0 while left < len(nums1) and right < len(nums2): if nums1[left] < nums2[right]: left += 1 elif nums1[left] == nums2[right]: res.append(nums1[left]) left += 1 right += 1 else: right += 1 return res问题2：
将较小的数组哈希计数，随后在另一个数组中根据哈希来寻找。 时间复杂度：O(max(n, m)) 空间复杂度：O(min(n, m))
思路二改写的，也不知道对不对
class Solution: def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]: n1, n2 = collections.Counter(nums1), collections.Counter(nums2) res = [] min_n = n1 if len(n1) <= len(n2) else n2 for i in min_n: temp = min(n1[i], n2[i]) while temp: res.append(i) temp -= 1 return res问题3：
通过归并外排将两个数组排序后再使用排序双指针查找
但是解法一中需要改造，一般说排序算法都是针对于内部排序，一旦涉及到跟磁盘打交道（外部排序），则需要特殊的考虑。归并排序是天然适合外部排序的算法，可以将分割后的子数组写到单个文件中，归并时将小文件合并为更大的文件。当两个数组均排序完成生成两个大文件后，即可使用双指针遍历两个文件，如此可以使空间复杂度最低。
