leetcode350--- 两个数组的交集

leetcode350— 两个数组的交集

关键字：哈希表，双指针

---

题目

给定两个数组，编写一个函数来计算它们的交集。

示例 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 的元素存储在磁盘上，内存是有限的，并且你不能一次加载所有的元素到内存中，你该怎么办？

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/intersection-of-two-arrays-ii

---

方法

1.哈希表

1. 新建一个列表用于储存交集的元素。
2. 对数组1遍历建立字典，字典的键为数组的元素值，对应的值为该元素在字典中出现的次数。
3. 遍历数组2，查找数组2的值是否在字典的键中出现且对应次数是否大于0，如果出现则加入列表并且将对应次数减1。
4. 返回列表

代码如下：

class Solution:
    def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
        hashmap = {}
        result = []
        for d in nums1:
            if d in hashmap.keys():
                hashmap[d] += 1
            else:
                hashmap[d] = 1
        for j in nums2:
            if j in hashmap.keys() and hashmap[j] > 0 :
                result.append(j)
                hashmap[j] -= 1
        return result

复杂度分析

• 时间复杂度：$O(m+n)$，需要遍历两个数组并进行操作。
• 空间复杂度：$O(\min (m,n))$， 对较短的数组进行哈希表的操作(后续改进后)，哈希表的大小不会超过较短的数组的长度， 并且生成了储存结果的列表。

官方答案哈希表计数写法：

m = collections.Counter()
for num in nums1:
	m[num] += 1

collections是Python内建的一个集合模块，提供了许多有用的集合类。以提供Python标准内建容器 dict , list , set , 和 tuple 的替代选择。

一个 Counter 是一个 dict 的子类，用于计数可哈希对象。它是一个集合，元素像字典键(key)一样存储，它们的计数存储为值。计数可以是任何整数值，包括0和负数。

所以使用这个Counter生成的对象可以使代码更简洁，提高一点速度。

hashmap = collections.Counter()
for num in nums1:
	hashmap[num] += 1

并且判断时更方便：

for j in nums2:
	if hashmap[j] > 0:
    	result.append(j)
        hashmap[j] -= 1

再改进：
针对数组1，数组2中较短的一个建立哈希表可以更节省空间，因此在开头加入对两个数组长度的判断。

if len(nums1) > len(nums2):
	return self.intersect(nums2, nums1)

改进后代码：

class Solution:
    def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
        if len(nums1) > len(nums2):
            return self.intersect(nums2, nums1)
        hashmap = collections.Counter()
        result = []
        for num in nums1:
            hashmap[num] += 1
        for j in nums2:
            if hashmap[j] > 0:
                result.append(j)
                hashmap[j] -= 1
        return result

---

2.双指针法

1. 对数组1，2先进行排序，从小到大排列，生成一个列表储存结果。

2. 对于排序好的数组利用双指针进行比较。
   初始时，两个指针分别指向两个数组的头部。每次比较两个指针指向的两个数组中的数字，如果两个数字不相等，则将指向较小数字的指针右移一位，如果两个数字相等，将该数字添加到列表，并将两个指针都右移一位。当至少有一个指针超出数组范围时，遍历结束。

代码如下：

class Solution:
    def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
        nums1 = sorted(nums1)
        nums2 = sorted(nums2)
        i = 0
        j = 0
        result = []
        n1 = len(nums1)
        n2 = len(nums2)
        while i < n1 and j < n2:
            if nums1[i] == nums2[j]:
                result.append(nums1[i])
                i += 1
                j += 1
            elif nums1[i] > nums2[j]:
                j += 1
            else:
                i += 1
        
        return result 

复杂度分析

• 时间复杂度：$O(m\log m+n\log n)$，其中 m 和 n 分别是两个数组的长度。对两个数组进行排序的时间复杂度是 $O(m\log m+n\log n)$，遍历两个数组的时间复杂度是 $O(m+n)$，因此总时间复杂度是 $O(m\log m+n\log n)$。
• 空间复杂度：$O(\min (m,n))$，储存交集的列表长度最大为两者中最小值。

---

总结

对于进阶部分的问题：

• 当两个数组有序时，采取方法2可以省去排序时间，并与方法比较起来更节省空间。少一个哈希表的存储空间。
• 当内存有限，无法一次加载数组2时，就无法高效地对数组2进行排序，使用方法1更好，并且方法1的查询操作可以每次访问部分元素并处理即可。
• 同理，当两个数组大小相差过大时，使用改进后的方法1更节省时间。