看完这篇文章你就彻底懂啦{保姆级讲解}-----(LeetCode刷题349两个数组的交集) 2023.5.9

这篇具有很好参考价值的文章主要介绍了看完这篇文章你就彻底懂啦{保姆级讲解}-----(LeetCode刷题349两个数组的交集) 2023.5.9。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

前言

本文章一部分内容参考于《代码随想录》----如有侵权请联系作者删除即可,撰写本文章主要目的在于记录自己学习体会并分享给大家,全篇并不仅仅是复制粘贴,更多的是加入了自己的思考,希望读完此篇文章能真正帮助到您!!!

算法题(LeetCode刷题349两个数组的交集)—(保姆级别讲解)

力扣题目链接

看完这篇文章你就彻底懂啦{保姆级讲解}-----(LeetCode刷题349两个数组的交集) 2023.5.9

分析题目:

什么是哈希表?

在线性表和树表的查找中,记录在表中的位置与记录的关键字之间不存在确定关系,因此,在这些表中查找记录时需要进行一系列的关键字比较。这类查找方法建立在”比较“的基础上,查找的效率取决于比较的次数。

那么怎么来解决这个问题,提高检索效率呢?

这里我们就需要使用到散列函数,它是一个把查找表中的关键字映射成该关键字对应的地址的函数,记为Hash(key) = Addr(这里的地址可以为数组下标、索引或者是内存地址等)

所以我们这里会使用到一种全新的数据结构叫做散列表也叫做哈希表,它能根据关键字而直接访问数据结构,也就是说,哈希表建立了关键字和存储地址之间的一种直接映射关系。

什么是冲突?

散列函数可能会把两个或两个以上的不同关键字映射到同一地址,称这种情况为冲突,这些发生冲突的不同关键字称为同义词。一方面要设计好的散列函数来尽可能的减少这样的冲突,另一方面,由于这样的冲突总是不可避免的,所以还要设计好处理冲突的方法。

常见的三种哈希结构

当我们想使用哈希法来解决问题的时候,我们一般会选择如下三种数据结构。

  1. 数组
  2. set (集合)
  3. map(映射)

这里数组就没啥可说的了,我们来看一下set
C++中,set 和 map 分别提供以下三种数据结构,其底层实现以及优劣如下表所示:
看完这篇文章你就彻底懂啦{保姆级讲解}-----(LeetCode刷题349两个数组的交集) 2023.5.9
std::unordered_set底层实现为哈希表,std::set 和std::multiset 的底层实现是红黑树,红黑树是一种平衡二叉搜索树,所以key值是有序的,但key不可以修改,改动key值会导致整棵树的错乱,所以只能删除和增加。

看完这篇文章你就彻底懂啦{保姆级讲解}-----(LeetCode刷题349两个数组的交集) 2023.5.9
std::unordered_map 底层实现为哈希表,std::map 和std::multimap 的底层实现是红黑树。同理,std::map 和std::multimapkey也是有序的(这个问题也经常作为面试题,考察对语言容器底层的理解)。

选择正确的哈希结构

当我们要使用集合来解决哈希问题的时候,优先使用unordered_set,因为它的查询和增删效率是最优的,如果需要集合是有序的,那么就用set,如果要求不仅有序还要有重复数据的话,那么就用multiset

那么再来看一下map ,在map 是一个key value 的数据结构,map中,对key是有限制,对value没有限制的,因为key的存储方式使用红黑树实现的。

由于在本题目中要求输出结果中的每一个元素一定是唯一的,所以也就说输出的结果是去重的,同时不考虑输出结果的顺序,所以我们直接选择unordered_set这个数据结构。

同时因为在本题中力扣官方增加了两个条件

看完这篇文章你就彻底懂啦{保姆级讲解}-----(LeetCode刷题349两个数组的交集) 2023.5.9

由上图可知,对数组大小和数组元素的大小做出了限制,正是因为有这两个限制,我们还可以使用数组来实现哈希表,即在本文章中我们会有两个版本实现。

算法思想(画图展示):

为了更能让大家了解该算法的算法思想,作者特意画了一张图供大家观看!!!

看完这篇文章你就彻底懂啦{保姆级讲解}-----(LeetCode刷题349两个数组的交集) 2023.5.9

算法思想(使用数组实现哈希表):

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        unordered_set<int> result_set; 
        int hash[1005] = {0}; 
        for (int num : nums1) { 
            hash[num] = 1;
        }
        for (int num : nums2) { 
            if (hash[num] == 1) {
                result_set.insert(num);
            }
        }
        return vector<int>(result_set.begin(), result_set.end());
    }
};

好!按照老样子,接下来开始详细讲解每行代码的用处,以及为什么这样写

unordered_set<int> result_set; 

声明一个unordered_set类型的数组,名称为result_set,用于存放我们最终的两个数组交集。之所以选择使用unordered_set,是因为自动会去重。不需要我们手动去重。

 int hash[1005] = {0}; 

由于本例中,数组大小限制在1000以内,所以我们可以提前声明一个1005的大小的数组,并且初始化赋值为0。同时,也可以是1004、1003等等,只需要大于1000即可。

 for (int num : nums1) { 
            hash[num] = 1;
        }

遍历nums1数组,根据nums1中的元素,则会对应的hash数组的下标里赋值1,例如nums1数组里有元素{2,5},则会在下标为2和下标为5的位置赋值1,方便比较nums2时使用。

for (int num : nums2) { 
            if (hash[num] == 1) {
                result_set.insert(num);
            }
        }

遍历nums2数组,根据nums2中的元素,去遍历hash数组,如果nums2中的元素对应于哈希表下标的值为1,则代表nums1nums2中的对应元素比较一致,即代表nums1中有nums2的元素。如果比较一致,则将该下标插入到unordered_set类型的result_set,以此类推。

 return vector<int>(result_set.begin(), result_set.end());

最终返回unordered_set类型的result_set

算法思想(使用unordered_set实现哈希表):

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        unordered_set<int> result_set; 
        unordered_set<int> nums_set(nums1.begin(), nums1.end());
        for (int num : nums2) {
           
            if (nums_set.find(num) != nums_set.end()) {
                result_set.insert(num);
            }
        }
        return vector<int>(result_set.begin(), result_set.end());
    }
};

好!按照老样子,接下来开始详细讲解每行代码的用处,以及为什么这样写

 unordered_set<int> result_set; 

声明一个unordered_set类型的数组,名称为result_set,用于存放我们最终的两个数组交集。之所以选择使用unordered_set,是因为自动会去重。不需要我们手动去重。

 unordered_set<int> nums_set(nums1.begin(), nums1.end());

将其nums1数组转换为unordered_set类型的哈希表,并且该哈希表为nums_set

for (int num : nums2) {
           
            if (nums_set.find(num) != nums_set.end()) {
                result_set.insert(num);
            }
        }

遍历nums2数组,如果发现nums2中的元素在nums_set中出现,则将对应的元素添加到unordered_set类型的 result_set中,代表两个数组中的交集元素。

unordered_set::find()函数是C++ STL中的内置函数,用于在容器中搜索元素。如果找到指定元素,它返回元素的迭代器,如果找不到指定元素,则返回指向unordered_set::end()的迭代器。所以判断与nums_set.end()是否相等即可。

 return vector<int>(result_set.begin(), result_set.end());

最终返回unordered_set类型的result_set

结束语

如果觉得这篇文章还不错的话,记得点赞 ,支持下!!!文章来源地址https://www.toymoban.com/news/detail-442011.html

到了这里,关于看完这篇文章你就彻底懂啦{保姆级讲解}-----(LeetCode刷题349两个数组的交集) 2023.5.9的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 看完这篇文章你就彻底懂啦{保姆级讲解}-----(LeetCode刷题242有效的字母异位词) 2023.4.25

    本文章一部分内容参考于《代码随想录》----如有侵权请联系作者删除即可,撰写本文章主要目的在于记录自己学习体会并分享给大家,全篇并不仅仅是复制粘贴,更多的是加入了自己的思考,希望读完此篇文章能真正帮助到您!!! 力扣题目链接 分析题目: 什么叫做字母异

    2024年02月06日
    浏览(43)
  • 看完这篇文章你就彻底懂啦{保姆级讲解}-----(LeetCode刷题142环形链表II) 2023.4.24

    本文章一部分内容参考于《代码随想录》----如有侵权请联系作者删除即可,撰写本文章主要目的在于记录自己学习体会并分享给大家,全篇并不仅仅是复制粘贴,更多的是加入了自己的思考,希望读完此篇文章能真正帮助到您!!! 力扣题目链接 分析题目: 其实本题目中主

    2024年02月05日
    浏览(51)
  • 看完这篇文章你就彻底懂啦{保姆级讲解}-----(LeetCode刷题203.707.206翻转链表) 2023.4.21

    本文章一部分内容参考于《代码随想录》----如有侵权请联系作者删除即可,撰写本文章主要目的在于记录自己学习体会并分享给大家,全篇并不仅仅是复制粘贴,更多的是加入了自己的思考,希望读完此篇文章能真正帮助到您!!! 力扣题目链接 关于这个算法思想,我在之

    2024年02月04日
    浏览(54)
  • 看完这篇文章你就彻底懂啦{保姆级讲解}-----(LeetCode刷题704、35、34数组二分查找) 2023.4.17

    本文章一部分内容参考于《代码随想录》----如有侵权请联系作者删除即可,撰写本文章主要目的在于记录自己学习体会并分享给大家,全篇并不仅仅是复制粘贴,更多的是加入了自己的思考,希望读完此篇文章能真正帮助到您!!! 数组是由n(n=1)个 相同类型 的数据元素

    2024年02月05日
    浏览(50)
  • 看完这篇文章你就彻底懂啦{保姆级讲解}-----(I.MX6U驱动UART串口通信) 2023.5.20

    串口是我们在开发过程中最常用到的外设,所以我们必须掌握。 串口驱动初始化部分 好!按照老样子,接下来开始详细讲解每行代码的用处,以及为什么这样写! 串口驱动初始化部分讲解开始: //将IO功能设置为UART1_RXD和UART1_TXD。 //配置UART1_TX_DATA、UART1_RX_DATA的IO属性。 先关

    2024年02月05日
    浏览(109)
  • ai绘画如何使用?看完这篇文章你就知道了

    对于艺术家和创作者来说,AI绘画可以作为一种实用的工具,提供灵感和创意的源泉。它可以分析和学习大量的艺术作品,从中汲取元素和风格,并以独特的方式重新组合和表达。这使得艺术家能够更快速地探索和实验不同的艺术风格,从而推动他们的创造力和艺术表达的边

    2024年02月09日
    浏览(57)
  • ai绘画生成方法有哪些?看完这篇文章你就知道了

    近年来,随着人工智能技术的不断发展和普及,AI 绘画作为一种新兴的艺术创作方式也逐渐被人们所认知。与传统绘画相比,AI 绘画可以通过计算机算法自动生成,具有高效、便捷的特点,同时也能够更好地满足一些特定场景的需求。 在过去,数字艺术家需要通过绘制、建模

    2024年02月15日
    浏览(57)
  • 怎么用ai绘画二次元拍同款?看完这篇文章你就懂了

    在我们的二次元世界里,每一张优质的插图都能够引发无尽的想象和瞬间的心动。而现如今,随着人工智能技术的飞速发展,ai绘画已经成为一个备受瞩目的领域。在使用ai绘画生成二次元作品时,ai绘画二次元描述词就显得相当重要。那么,究竟ai绘画二次元描述词怎么写呢

    2024年02月16日
    浏览(52)
  • 中缀表达式转后缀表达式看完这一篇文章你就懂了

    一、什么是中缀表达式 二、什么是后缀表达式 三、后缀转中缀具体思路 四、代码实现 中缀表达式就是我们常用的算术表达方式,例如 (12+34)*5 ,运算符在两个数的中间,但是对于中缀表达式来说括号和加减乘除使得问题对于计算机非常复杂,为了有效的处理他们,波兰逻辑

    2024年02月08日
    浏览(51)
  • 你真的学懂if语句了嘛,看完这篇文章你一定会让你有所收获,彻底玩转if语句!

    🎬 鸽芷咕 :个人主页  🔥 个人专栏 :《C语言初阶篇》 《C语言进阶篇》 ⛺️生活的理想,就是为了理想的生活!    🌈 hello! 各位宝子们大家好啊,相信大家都多多少少了解过if语句吧,但是你真的有了解过,所有if语句的细节吗?学完这篇文章你将知道if语句的所有知识

    2024年02月11日
    浏览(52)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包