九眼智能信息过滤 大数据助力产品升级解析
580
2022-10-18
刷题力扣349-两个数组的交集
这道题代码随想录用的是哈希数据结构,什么时候用哈希表,哈希表都是用来快速判断一个元素是否出现在集合里,相对于枚举的话,哈希表的时间复杂度只有O(1)。
常见的三种哈希结构
数组set(集合)map(映射)
当出现快速判断一个元素是否出现在集合里的时候,就要考虑哈希法,牺牲空间换取时间。
题目描述:
题意:给定两个数组,编写一个函数来计算它们的交集。
说明: 输出结果中的每个元素一定是唯一的。 我们可以不考虑输出结果的顺序。
在不考虑数量的情况下,假设数据有无穷大,我们可以用set的哈希结构去解这道题。在java中使用set,可以得到一个不包含重复元素的集合,而且set无序,且允许出现null元素。
set方法:
boolean add(E e) //如果 set 中尚未存在指定的元素,则添加此元素(可选操作)。boolean addAll(Collection extends E> c) //如果 set 中没有指定 collection 中的所有元素,则将其添加到此 set 中(可选操作)。void clear() //移除此 set 中的所有元素(可选操作)。boolean contains(Object o) //如果 set 包含指定的元素,则返回 true。boolean containsAll(Collection> c) //如果此 set 包含指定 collection 的所有元素,则返回 true。boolean equals(Object o) //比较指定对象与此 set 的相等性。int hashCode() //返回 set 的哈希码值。boolean isEmpty() //如果 set 不包含元素,则返回 true。Iterator
解题思路:
将nums1的集合元素放到一个set集合里,然后去遍历nums2集合元素,如果nums2集合元素在set集合里出现,我们就可以把该元素的下标放到结果的set集合里。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
力扣这道题后来把数据范围限制在1000以内,那么可以用数组来写,java如果用数组做哈希结构的话,代码方法如下:
class Solution { public int[] intersection(int[] nums1, int[] nums2) { if(nums1 == null || nums1.length == 0 || nums2 == null || nums2.length == 0){ return new int[0]; } int[] hash = new int[1005]; Set
版权声明:本文内容由网络用户投稿,版权归原作者所有,本站不拥有其著作权,亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容,请联系我们jiasou666@gmail.com 处理,核实后本网站将在24小时内删除侵权内容。
发表评论
暂时没有评论,来抢沙发吧~