【Leetcode】349. 两个数组的交集

题意

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

说明: 输出结果中的每个元素一定是唯一的。 我们可以不考虑输出结果的顺序。 

思路

        这道题目,主要要学会使用一种哈希数据结构:unordered_set,这个数据结构可以解决很多类似的问题。

        注意题目特意说明:输出结果中的每个元素一定是唯一的,也就是说输出的结果的去重的, 同时可以不考虑输出结果的顺序

        这道题用暴力的解法时间复杂度是O(n^2),那来看看使用哈希法进一步优化。

        那么用数组来做哈希表也是不错的选择,但是要注意,使用数组来做哈希的题目,是因为题目都限制了数值的大小。

        而这道题目没有限制数值的大小,就无法使用数组来做哈希表了。

        而且如果哈希值比较少、特别分散、跨度非常大,使用数组就造成空间的极大浪费。

        此时就要使用另一种结构体了,set ,关于set,C++ 给提供了如下三种可用的数据结构:

  • std::set
  • std::multiset
  • std::unordered_set

std::set和std::multiset底层实现都是红黑树,
std::unordered_set的底层实现是哈希表,
使用unordered_set 读写效率是最高的,并不需要对数据进行排序,而且还不要让数据重复,所以选择unordered_set。

思路如图所示:

拓展

那有同学可能问了,遇到哈希问题我直接都用set不就得了,用什么数组啊。

直接使用set 不仅占用空间比数组大,而且速度要比数组慢,set把数值映射到key上都要做hash计算的。

不要小瞧 这个耗时,在数据量大的情况,差距是很明显的。

class Solution(object):
    def intersection(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: List[int]
        """
        # 使用哈希表存储一个数组中的所有元素
        table = {}
        for num in nums1:
            table[num] = table.get(num, 0) + 1
        
        # 使用集合存储结果
        res = set()
        for num in nums2:
            if num in table:
                res.add(num)
                del table[num]
        
        return list(res)

table.get(num, 0) 表示获取键 num 对应的值,如果 num 存在则返回其值,否则返回 0。

 

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/118527.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

MYSQL:主从复制简述

(图片来自于马士兵教育) 从节点的I/O线程会请求主节点的Binlog,并且将得到的Binlog写入到本地relay_log(中继日志)中,SQL线程会读取realy_log中的日志文件,并且解析成SQL逐行执行。 主库会生成…

XSS漏洞利用工具BeEF

BeEF是Browser Exploitation Framework的缩写。随着人们越来越多地关注针对包括移动客户端在内的客户端的网络传播攻击,BeEF使专业的渗透测试人员可以使用客户端攻击向量来评估目标环境的实际安全状况。与其他安全框架不同,BeEF超越了硬化的网络边界和客…

win11下使用VMmare设置CentOS7里面的静态IP

1,win11上的VMware 8 设置 2,选择VMmare上的虚拟网络编辑进行设置 #3,接下来进入虚拟机设置(就是进入CentOS7 打开终端 右键 Open Terminal ) # 切换root su root #ksana #编辑网络配置文件 vi /etc/sysconfig/networ…

【LeetCode:318. 最大单词长度乘积 | 模拟 位运算】

🚀 算法题 🚀 🌲 算法刷题专栏 | 面试必备算法 | 面试高频算法 🍀 🌲 越难的东西,越要努力坚持,因为它具有很高的价值,算法就是这样✨ 🌲 作者简介:硕风和炜,…

nn.embedding函数详解(pytorch)

提示:文章附有源码!!! 文章目录 前言一、nn.embedding函数解释二、nn.embedding函数使用方法四、模型训练与预测的权重变化探讨 前言 最近发现prompt工程(如sam模型),也有transform的detr模型等都使用了nn.Embedding函…

GB28181学习(十五)——流传输方式

前言 基于GB/T28181-2022版本,实时流的传输方式包括3种: UDPTCP被动TCP主动 UDP 流程 注意: m字段指定传输方式为RTP/AVP; 抓包 SIP服务器发送INVITE请求; INVITE sip:xxx192.168.0.111:5060 SIP/2.0 Via: SIP…

【C++】智能指针【内存泄漏|智能指针原理及使用|RAII】

目录 1、了解内存泄露 1.1 内存泄漏的定义及危害 1.2 内存泄漏分类(了解) 1.3 如何检测内存泄漏(了解) 1.4如何避免内存泄漏 2、智能指针的引出 3、智能指针的使用及原理 3.1 RAII 3.2 智能指针的原理 3.3 std::auto_pt…

skynet学习笔记01— skynet开发环境搭建(超详细)与第一个skynet程序

00、参考资料 https://blog.csdn.net/qq769651718/category_7480207.html 01、前置准备 开发所在目录 mhzzjmhzzj-virtual-machine:~/work/skynetStudy$ pwd /home/mhzzj/work/skynetStudy前置准备 mhzzjmhzzj-virtual-machine:~/work/skynetStudy$ sudo apt install lua5…

手动关闭PS中的TopazStudio2的登录窗口

2021 adobe photoshop Topaz Studio 2 不是使用防火墙出站规则,是手动关闭的解决方案 点击社区-切换用户,登录窗口会出现X,可以手动关闭

【flutter no devices】

1.在环境变量增加 ANDROID_HOME 值为:C:\Users\Administrator\AppData\Local\Android\Sdk (Android sdk 位置) 2 环境变量的path里面增加2个值: %ANDROID_HOME%\platform-tools %ANDROID_HOME%\tools 3 打开cmd,或者在Android st…

uniapp使用抖音微信自定义组件

tt.vue中使用video-player组件 用到的目录如下: pages.json {"path": "pages/Tabbar/tt/tt","style": {"navigationBarTitleText": "","enablePullDownRefresh": false,// 使用自定义组件"using…

使用R语言构建HTTP爬虫:IP管理与策略

目录 摘要 一、HTTP爬虫与IP管理概述 二、使用R语言进行IP管理 三、爬虫的伦理与合规性 四、注意事项 结论 摘要 本文深入探讨了使用R语言构建HTTP爬虫时如何有效管理IP地址。由于网络爬虫高频、大量的请求可能导致IP被封禁,因此合理的IP管理策略显得尤为重要…

【JAVA学习笔记】63 -坦克大战1.3-敌方发射子弹,击中坦克消失并爆炸,敌人坦克随机移动,规定范围限制移动

项目代码 https://github.com/yinhai1114/Java_Learning_Code/tree/main/IDEA_Chapter18/src/com/yinhai/tankgame1_3 〇、要求 增加功能 1.让敌人的坦克也能够发射子弹(可以有多颗子弹) 2.当我方坦克击中敌人坦克时,敌人的坦克就消失,如果能做出爆炸效果更好. …

人工智能-卷积神经网络

从全连接层到卷积 我们之前讨论的多层感知机十分适合处理表格数据,其中行对应样本,列对应特征。 对于表格数据,我们寻找的模式可能涉及特征之间的交互,但是我们不能预先假设任何与特征交互相关的先验结构。 此时,多层感…

Java锁常见面试题

图片引用自:不可不说的Java“锁”事 - 美团技术团队 1 java内存模型 java内存模型(JMM)是线程间通信的控制机制。JMM定义了主内存和线程之间抽象关系。线程之间的共享变量存储在主内存中,每个线程都有一个私有的本地内存,本地内存中存储了该…

计算机毕业设计java+springboot+vue的旅游攻略平台

项目介绍 本系统结合计算机系统的结构、概念、模型、原理、方法,在计算机各种优势的情况下,采用JAVA语言,结合SpringBoot框架与Vue框架以及MYSQL数据库设计并实现的。员工管理系统主要包括个人中心、用户管理、攻略管理、审核信息管理、积分…

Crypto(9)[MRCTF2020]keyboard

下载题目,看看里面是什么 这是什么鬼,由题目可以获得线索,keyboard,不是键盘吗,然后看了看别人写的wp,发现是九键,有几个数字对应的密文就是第几个字母 比如第一个6,对应的字母是mno&#xff0c…

80个10倍提升Excel技能的ChatGPT提示

你是否厌倦了在使用Excel时感觉像个新手?你是否想将你的技能提升到更高的水平,成为真正的Excel大师?嗯,如果你正在使用ChatGPT,那么成为Excel专家简直易如反掌。 你只需要了解一些最有用的Excel提示,就能在…

龙迅LT8619C HDMI转LVDS/RGB/BT656/BT1120/BT601

LT8619C 描述: Lontium的LT8619C是一款高性能的HDMI/双模式DP接收器芯片,符合HDMI 1.4规范。TTL输出可支持RGB、BT656、BT1120,输出分辨率最多可支持4Kx2K30Hz。为了方便地实现一个多媒体系统,LT8619C支持8通道高质量的I2S音频或…

CSDN每日一题学习训练——Java版(两数相加、二叉树的锯齿形层序遍历、解数独)

版本说明 当前版本号[20231106]。 版本修改说明20231106初版 目录 文章目录 版本说明目录两数相加题目解题思路代码思路补充说明参考代码 二叉树的锯齿形层序遍历题目解题思路代码思路参考代码 解数独题目解题思路代码思路补充说明参考代码 两数相加 题目 给你两个 非空 的…