【leetcode初级】6-两个数组的交集

• 给定两个数组，写一个方法来计算它们的交集。

例如:
给定 nums1 = [1, 2, 2, 1], nums2 = [2, 2], 返回 [2, 2].
注意：
输出结果中每个元素出现的次数，应与元素在两个数组中出现的次数一致。 我们可以不考虑输出结果的顺序。
跟进:
如果给定的数组已经排好序呢？你将如何优化你的算法？
如果 nums1 的大小比 nums2 小很多，哪种方法更优？
如果nums2的元素存储在磁盘上，内存是有限的，你不能一次加载所有的元素到内存中，你该怎么办？

• 思路：
  交集就是同时存在A和B里的元素集合。根据概念即明白需要对一个数组遍历，然后去看它是否存在另一个数组里。这里需要注意的是因为会出现重复的元素，所以需要注意去掉已经匹配到交集里的元素。根据这个思路，首先使用哈希表存储nums2里每个值的出现个数，Python里用dict实现，接着遍历nums1，逐个匹配，如果找的到就用add到交集中并减1 nums2的个数。时间复杂度为O(n), 空间复杂度O(n)。
• 代码：

class Solution(object):
    def intersect(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: List[int]
        """
        intersection = []
        nums2_dict = {}
        for num in nums2:
            if num not in nums2_dict.keys():
                nums2_dict[num] = 1
            else:
                nums2_dict[num] += 1
        for num in nums1:
            if num in nums2_dict.keys() and nums2_dict[num] != 0:
                intersection.append(num)
                nums2_dict[num] -= 1
        return intersection

• 这样做提交代码后耗时达到84ms, 低于平均，主要得进行多次遍历和查找。根据题目提示，我们换用排序数组试试。如果已经排好序，这道题就非常简单，两个指针往后面不断地去匹配就行，如果A里比B大，就让A指针停下，B的指针继续走，直到相等。这样时间复杂度主要在排序Timesort O(n*log(n)), 比较的复杂度只有O(n)。空间复杂度O(1)。提交耗时只有40ms。
• 代码：

class Solution(object):
    def intersect(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: List[int]
        """
        nums1.sort()
        nums2.sort()
        intersection = []
        i = 0
        j = 0
        while i < len(nums1) and j < len(nums2):
            if nums1[i] == nums2[j]:
                intersection.append(nums1[i])
                i += 1
                j += 1
            elif nums1[i] < nums2[j]:
                i += 1
            else:
                j += 1
        return intersection

看提交记录应该有更快的方法，待思考补充。