大家好呀,我是帅蛋。
今天来解决两个数组的交集,继续通过实战题目的巩固,玩转哈希表!
LeetCode 349:两个数组的交集
题意
给定两个数组,计算它们的交集。
示例
输入:nums1 = [4, 9, 5],nums2 = [9, 4, 9, 8, 4]
输出:[9, 4]
提示
- 输出结果中的每个元素一定是唯一的。
- 我们可以不考虑输出结果的顺序。
题目解析
水题,难度简单。
就一句话:求两个数组的交集,直白点儿就是【nums2 的元素是否在 nums1 中】。
需要注意一下“提示”里讲的:输出结果中的每个元素一定是唯一的,翻译一下就是去重输出。
这道题为啥能用哈希做呢?
我在之前【LeetCode202 快乐数】中讲过:在一堆数中查找一个数,当然是扔出哈希,毕竟是查找中的秒男,时间复杂度为 O(1)。
这道题和快乐数有些相似的地方:这道题同样也没限制数值的大小,所以就不能用数组来做哈希表。
碰到这种对目前来说是未知数值大小的情况,我们可以使用集合 set 来解决。
用 set 爽归爽,在这里我建议还是不要直接用库函数。
大家用的编程语言可能不尽相同,最好是用编程语言自带的数据结构来模拟一下,毕竟对于初学者来说,还是得脚踏实地一步步的搞。
图解
以 nums1 = [4, 9, 5],nums2 = [9, 4, 9, 8, 4] 为例。
首先初始化一个哈希表和一个结果列表。
# 初始化哈希表 hash = {} # 初始化结果列表,存放最后结果 res = []
第一步,遍历数组 nums1,将出现的数存进哈希表中。
nums1 数组中,第 1 个元素为 4,将其加入哈希表,对应数值置为 1。
# 哈希表 key 为 nums1 数组中的数,value 为值 for i in nums1: if not hash.get(i): hash[i] = 1
因为【输出结果中的每个元素一定是唯一的】,所以对于 key 所对应的 value 来说“数值是多少”就无所谓了,所以在本题中,不管某个元素在数组中出现多少次,我把 value 都置为 1。
遍历完数组 nums1,哈希表如下图所示:
第二步,遍历 nums2 数组,nums2 数组中的元素如果出现在哈希表中,则证明是和 nums1 数组相交的元素,则加入结果列表中。
nums2 数组中,第 1 个元素为 9,9 在哈希表中,则元素 9 加入结果列表,哈希表中该元素置为 0。
# 遍历 nums,如果 nums2 数组中的数出现在哈希表中,对应数放入结果列表,对应 value 值置-为0 for j in nums2: if hash.get(j): res.append(j) hash[j] = 0
同样遍历完 nums2,最后的结果变为下图所示:
res 就是最终的结果。
本题解遍历了 nums1 和 nums2 数组,所以时间复杂度为 O(n + m),n 和 m 分别为两个数组的长度。
额外建了一个哈希表,所以空间复杂度为 O(max(n, m))。
代码实现
Python 代码实现
class Solution: def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]: # 有一个数组为空,则交集为空 if not nums1 or not nums2: return [] # 初始化哈希表 hash = {} # 初始化结果列表,存放最后结果 res = [] # 哈希表 key 为 nums1 数组中的数,value 为值 for i in nums1: if not hash.get(i): hash[i] = 1 # 遍历 nums,如果 nums2 数组中的数出现在哈希表中,对应数放入结果列表,对应 value 值置-为0 for j in nums2: if hash.get(j): res.append(j) hash[j] = 0 return res
Java 代码实现
import java.util.HashSet; import java.util.Set; class Solution { public int[] intersection(int[] nums1, int[] nums2) { if (nums1 == null || nums1.length == 0 || nums2 == null || nums2.length == 0) { return new int[0]; } Set<Integer> set1 = new HashSet<>(); Set<Integer> resSet = new HashSet<>(); //遍历 nums1 for (int i : nums1) { set1.add(i); } //遍历nums2,判断哈希表中是否存在该元素 for (int i : nums2) { if (set1.contains(i)) { resSet.add(i); } } int[] resArr = new int[resSet.size()]; int index = 0; for (int i : resSet) { resArr[index++] = i; } return resArr; } }
图解两个数组的交集到这就结束辣。
这是哈希实战的第 4 题,不知道大家有没有发现我的小心思:
第 1 题【LeetCode242 有效的字母异位词】和第 2 题【LeetCode383 赎金信】,第 3 题【LeetCode202 快乐数】和两个数组的交集是一类题。
相同类型的题刷多了,你就会发现,最后其实在你脑子里记住的不是实现这道题的代码,而是解这道题的思路。
等什么时候出现类似“这道题我见过,我知道用这样哪样的方法可以做出来”,小婊贝们就快出师了。
大家加油!也记得帮我点赞 + 在看呀。
我是帅蛋,我们下次见!