LeetCode 349:两个数组的交集
题意
给定两个数组,计算它们的交集。
示例
输入:nums1 = [4, 9, 5],nums2 = [9, 4, 9, 8, 4]
输出:[9, 4]
提示
输出结果中的每个元素一定是唯一的。 我们可以不考虑输出结果的顺序。
题目解析
求两个数组的交集,直白点儿就是【nums2 的元素是否在 nums1 中】。
第一种解法
这道题字符串 num1 和 num2 仅包含1000以内,数字就固定的 1000个。
(不要我问我为什么1000以内,因为你has设到100以内报错~)
这种定长的范围且和字符次数相关,用哈希妥妥的没问题。
第一种解法 使用的哈希函数 f(key) = key - 0 。 (这道题思路沿用了242有效字母的异位词~) 哈希函数找好,下面的就很简单:
- 遍历字符串 num1,哈希表hash1对应的字符值加。
- 遍历字符串 num2,哈希表hash2对应的字符值加。
- 判断哈希表hash1不为0,并且hash2也不为0,则把重复的数字输送到result序列
代码实现
class Solution: def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]: hash1=[0]*1000 for i in range(len(nums1)): hash1[nums1[i]-0] +=1 hash2=[0]*1000 for i in range(len(nums2)): hash2[nums2[i]-0] +=1 result=[] for i in range(1000): if hash1[i] != 0: if hash2[i] != 0: result.append(i) return result 复制代码
网络异常,图片无法展示
|
第二种解法
这道题同样也没限制数值的大小,所以就不能用数组来做哈希表。
碰到这种对目前来说是未知数值大小的情况,我们可以使用集合 set 来解决。
代码实现
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