两个数组的交集 II
给定两个数组，写一个方法来计算它们的交集。
例如: 给定 nums1 = [1, 2, 2, 1], nums2 = [2, 2], 返回 [2, 2].
注意：
- 输出结果中每个元素出现的次数，应与元素在两个数组中出现的次数一致。
- 我们可以不考虑输出结果的顺序。
跟进:
- 如果给定的数组已经排好序呢？你将如何优化你的算法？
- 如果 nums1 的大小比 nums2 小很多，哪种方法更优？
- 如果nums2的元素存储在磁盘上，内存是有限的，你不能一次加载所有的元素到内存中，你该怎么办？
初步解答¶
首先先考虑如何实现这个算法。从题目看是要求返回交集数组，需要注意的地方题目也已经给标注出来了。
这边不要求输出结果顺序，所以比较简单。因为要求交集元素保留在结果数组中的次数，所以 set 结构无疑是不适用的。
一开始想到利用数组的特性来做，得出以下代码：
In [1]:
class Solution:
def intersect(self, nums1, nums2):
"""
:type nums1: List[int]
:type nums2: List[int]
:rtype: List[int]
"""
ret = []
rng = nums1
in_arr = nums2
if len(nums1) < len(nums2):
rng = nums2
in_arr = nums1
for i in rng:
if i in in_arr:
ret.append(i)
in_arr.remove(i)
return ret
但是这样做有个缺点，在一个未排序的数组中，判断是否存在 in 和 remove 操作复杂度都为 O(n), 这将会带来额外开销。
所以，其实这个算法在数据量比较大的情况下是不适用的。
优化¶
这边就按给定的跟进思路来继续优化。
如果给定的数组是已经优化好的呢，或者一个数组要比另一个数组小的多。
从这一点上考虑，假定是排序好的数组，可以通过比较两个数组相同下标的值来判断，如果存在下标不等的情况则其中一个数组下标前移。
根据这个思路，写出以下代码：
In [2]:
class Solution:
def intersect(self, nums1, nums2):
"""
:type nums1: List[int]
:type nums2: List[int]
:rtype: List[int]
"""
nums1.sort()
nums2.sort()
ret = []
i = 0
j = 0
while i < len(nums1) and j < len(nums2):
z = nums1[i] - nums2[j]
if z == 0:
ret.append(nums1[i])
i += 1
j += 1
elif z > 0:
j += 1
else:
i += 1
return ret
在这个算法里，首先先对两个数组进行排序，然后在循环结束之前比较两个下标的值，如果值相等则说明存在相同项，下标均前移；如果不等则只前移其中一个。
这样的好处在于，算法的循环始终为较小数组的长度n，这里就解决了刚刚的第二问。
缺点在于，我们需要对该数组进行排序。不过python中的sort本身就是混合了多种排序方法的一个高效排序手段，性能上虽有一点开销，但是无疑比第一种解答要高。
针对第三个问题¶
针对第三个问题，如果数组特别大的情况下，那么就难以完成排序操作。这边暂时没有什么思路。。后续想到再进行补充
Comments !