【LeetCode哈希表#2】两个数组的交集(Set+数组)

两个数组的交集

力扣题目链接(opens new window)

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

349. 两个数组的交集

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

思路

哈希表最擅长解决的一类问题是:

给一个元素,判断该元素在某个集合中是否出现过

本题也是非常符合哈希表的使用场景

选择合适的哈希表也是使用哈希方法时的关键

之前有提到,哈希表的实现大致有三类:数组、set、map

数组使用于长度有限的数据(最好是1000个以下),如果哈希值比较少、特别分散、跨度非常大,使用数组就造成空间的极大浪费。

而set则可用于大规模的数据(例如上亿级别)

本题在LeetCode更新后加了限制,因此可以用数组来做也可以用set来做

set

set这种数据结构在C++(std::set【红黑树】、std::multiset【红黑树】、std::unordered_set【哈希表】)和Java(主要是HashSet【数组+链表+红黑树】,当然还有别的实现类)中的特性是类似的

即:

  • set是无序的(添加和取出的顺序不一致),且没有索引

  • set中不允许有重复元素(会自动去重),因此最多包含一个null

  • set不能使用普通for循环遍历,要用迭代器增强for循环

那么实际这题就变成了如何使用set接口的一个演示例题了

首先,新建一个set1,这里选用HashSet(cpp版本用unordered_set),遍历输入的nums1并存入set1

此时,set1中存放的数据就是去重后nums1中的元素

然后,再创建一个set2用于存放比较后的交集元素

遍历nums2,使用每个元素去set1中查询是否有相同的,有就保存到set2

数组

使用数组作为哈希表

遍历nums1,按当前元素在数组中对应下标处标记

如:

nums1 = {1,3,5,9}
         ↑
         
数组 = {0,1,0,...,0}
======================
nums1 = {1,3,5,9}
           ↑
           
数组 = {0,1,0,1,..,0}
======================

把nums1中所有元素在数组中标记后,当前数组就变成了一个哈希表。

输入为:"0~数组长度" 范围内的整数

输出为:一个布尔值,表示输入是否存在

之后,再用同样的方法遍历nums2,用遍历的元素作为下标到数组中查询,如果返回1,则将当前元素添加到一个set中(这样可以去除重复出现的元素)

代码

只使用set

Java版

import java.util.HashSet;
import java.util.Set;


class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        Set<Integer> set1 = new HashSet<>();
        Set<Integer> set2 = new HashSet<>();
        //遍历nums1,将元素添加到set1
        // //增强for
        // for(int i : nums1){
        //     set1.add(i);
        // }
        for(int i = 0; i < nums1.length; i++){
            set1.add(nums1[i]);
        }
        //遍历nums2,将所得元素与set1中的对比,相同则存入set2
        ////增强for
        // for(int i : nums2){
        //     if(set1.contains(i)){
        //         set2.add(i);
        //     }
        // }
        for(int i = 0; i < nums2.length; i++){
            if(set1.contains(nums2[i])){
                set2.add(nums2[i]);
            }
        }
        //将set转换为数组对象返回
        return set2.stream().mapToInt(x -> x).toArray();

    }
}

注意点:

1、使用set需要自行导入包

import java.util.HashSet;
import java.util.Set;

2、JavaAPI中Set接口常用方法

  • .add,用于添加数据
  • .contains,查询数据是否存在于set中
  • .stream(),将源数据----包括集合、数组等转换成流
  • .mapToInt(x -> x),将一个流中的元素转换为 int 类型
  • .toArray(), 转换类型为一个数组(Object)

CPP版

待更新
数组

Java版

import java.util.HashSet;
import java.util.Set;

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        Set<Integer> set4save = new HashSet<>();
        int[] hash = new int[1002];//题目限制了nums的大小在1000以下,因此数组可以设置1000左右
        //遍历nums1,使用数组hash构建哈希表
        for(int num : nums1){
            hash[num] = 1;
        }
		//遍历nums2,用元素值作为下标查询哈希表
        for(int num : nums2){
            if(hash[num] == 1){
                set4save.add(num);
            }
        }
        //将set转换为数组对象返回
        return set4save.stream().mapToInt(x -> x).toArray();
    }
}

CPP版

敬请期待
本文转载于网络 如有侵权请联系删除

相关文章

  • CSS命名法BEM与scoped、module

    刚入行前端的时候,看见了百度的前端代码规范,到现在只是其中的几个点一直有在注意。有兴趣可以看看: 百度前端编码规范CSS命名其实挺随意的,使用驼峰、-、_都可以,并不影响使用,常用的应该是-和下划线_连接。我一直使用的是-,因为各大UI库或者是CSS库都是使用-,这应该也成为一个标准规范。CSS挺容易造成样式污染的,每个模块或者页面之间,总有一些命名容易相同,解决也简单,用权重或者重写,只是这种场景有时候还是挺头疼。scopedvue中,style都会加上scoped,打包之后标签上面会有很多data-v-4df10a14,而CSS是.test[data-v-65a7937e]。 平时我们不会关注这个,这其实是CSS的属性选择器,打包的时候给每个标签都添加一个唯一的data-v-hash。module这个没用过,也没有去弄个demo,大致意思就是可以自己定义编译的规则,把类名编译成只对当前组件有效的字符串,可以是hash字符,也可以是带组件名类名加hash字符串,最终就是得到唯一的类名。test.vue .test-button{} //编译成 .test_test-button_4

  • linux之zgrep查找压缩包文件文本

    但如果想要过滤Nginx的access_log.gz的压缩文件的内容,如果先解压,然后过滤出有用的文本,再把文件压缩回去,这就变的非常不方便。传统做法>gunzipaccess_log.gz >grep"/rumenz"access_log >gzipaccess_log复制使用zgrep来一步完成>zgrep"/rumenz"access_log.gz复制zgrep也可以指定多个文件同时进行搜索过滤>zgrep"/rumenz"access_log.gzerror.gz复制查找.tar.gz文件>zgrep-anH"rumenz"rumenz.tar.gz rumenz.tar.gz:9:rumenz复制-a让其二进制文件当做文本处理-n显示行号-H显示文件名

  • Windows 11正式发布,Win10用户可免费升级

    2021年6月24日晚11点,微软举办了主题为“what'snextforWindows”的专场发布会。微软全球副总裁PanosPanay宣布Windows11正式发布。我们先来看个短片来直观了解新的Windows11:Window10免费升级这应该是大家最关心的事情了。符合条件的Windows10用户将免费升级到Windows11,这一活动会持续到2022年。预计会在秋季开始这一活动。全新UI看了短片之后,最直观的感受就是UI变了。图标更加扁平化,为人诟病的磁铁设计被放弃了,任务栏默认居中,非常接近MacOS的dock任务栏。更加开放的应用商店在Windows11中应用商店是我认为变化最大的。苹果AppStore的成功让微软意识到应用商店的重要性。为此微软构建了一个更加开放的应用商店,不再单单支持分发UWP程序,还支持Java程序和Atom程序。为了吸引开发者来构建应用商店的生态,微软将允许应用程序开发者自由选择支付机制,例如使用开发者自己的内置支付系统,并且允许他们保留100%的收益。安卓应用直接原生运行安卓应用将通过AmazonStore的形式登录到Windows11平

  • 和 lvgo 一起学设计模式(二十二)行为型之访问者模式

    访问者模式将作用于某种数据结构中的各元素的操作分离出来封装成独立的类,使其在不改变数据结构的前提下可以添加作用于这些元素的新的操作,为数据结构中的每个元素提供多种访问方式。它将对数据的操作与数据结构进行分离,是行为类模式中最复杂的一种模式。 刚看到这个模式的时候,我人都傻了,完全不知道说的是啥,直到看了近5份资料!才搞清楚这个设计模式,不愧是最复杂的一种,我也这样觉得。不过千万别被复杂吓到,捋清了之后,还是比较简单的。开门见山访问者模式“人如其名”,就是说不同的访问者对同一个对象的访问结果不同。为什么会不同呢?因为这个访问者是我们自己定义的,我们就想让他不同?。而实际情况更是如此。我通过几份资料总结下来,这个访问者模式所谓的访问者其实就是我们想要控制的访问权限一样。因为任何一个“访问者”都可以看到具体数据的全部内容,他只是选择性的"不看“,这样便区分开了”访问者“关注的内容,或者**”限制“了”访问者“的权限**。可能我说的有点绕,有点抱歉,我再简化一下这个内容。网络用语抛开表象看本质如果我们抛开访问者模式这些专业的定义,单纯的去理解这个访问者模式要表达的意思,我觉得用一个东

  • 【SAP FICO系列】SAP FICO 凭证字段的可见强制输入的配置

    在sap可以通过“字段状态变式”和“定义过帐码-字段状态”来控制财务凭证的是否显示,是否强制输入,可选输入。 设置步骤和相关TCODE:Step1:OB41-MaintainAccountingConfiguration:PostingKeysIMG-〉财务会计->财务会计的全局设置->凭证->控制->定义过账码->Step2:OBC4-MaintainFieldStatusGroup.Thegroupcanbeassignedtoaccount.Thegroupcanbeassignedtoaccount. FieldStatusGroupAllowsyoutohideoraddfieldstofinancialtransactions,dependingonthePostingKeyandFieldStatusGroup,assignedtotheaccount.IMG-〉财务会计->财务会计的全局设置->凭证->控制->维护字段状态变式Step3:OBC5-AssignCompanyCodetoFieldStatusVaria

  • 150+行Python代码实现带界面的数独游戏

    150行代码实现图形化数独游戏Github地址,欢迎各位大佬们fork、star啥的,感谢;今天闲着没事干,以前做过html+js版的数独,这次做个python版本的,界面由pygame完成,数独生成由递归算法实现,由shuffle保证每次游戏都是不一样的情况,havefun;功能列表:图形化的数独游戏;python实现,依赖pygame库;随机生成游戏,每次运行都不一样;数字填入后的正确性判断以及颜色提示;显示剩余需填入的空格,已经操作的次数;难度可选,通过修改需要填入的空的数量;游戏界面初始界面过程中界面运行方式pythonmain.py15复制这里的15表示需要填入的空格数量为15,理论上这个值越大,难度就越高,大家可以随机调整,或者设置容易、简单、困难、地狱等对应不同的值即可,很方便修改;程序分析界面部分这部分很简单的通过pygame来实现,主要使用了其中的主循环、鼠标键盘监听、画矩形线条、字体、颜色控制等,理解起来很容易,对于这部分不太熟悉的同学,这样理解就好:pygame的主循环中一方面负责接收用户输入,一般就是鼠标和键盘,另一方面负责实时更新界面显示内容;对于界面上各部分

  • ​一分钟开始持续集成之旅系列之:微信公众号服务器端应用(以 Java 后端为基础)

    作者:CODING-朱增辉前言本文是CODING持续集成自定义构建节点功能的使用教程,通过一个为微信公众号启用开发配置的Demo演示,讲解如何接入自定义构建节点,如何使用自定义构建节点进行构建、测试、部署服务器。准备工作环境本文会使用到如下工具,请确认已安装,或者根据链接的文档进行安装。gitJavaMaven开发微信公众号还需要提前准备好下面两项资源。微信公众号微信公众号可以在微信公众平台官网申请,平台也提供了详细的开发帮助文档。服务器这里的服务器指的是能够让微信服务器访问到的计算机,用来运行本文的服务端程序。很多公司都提供了云服务器租赁,还是很方便获取的。这里推荐腾讯云平台的CVM,临时用的话,竞价实例真的很划算。代码本文重点是介绍CODING平台持续集成自定义构建节点功能,具体的业务逻辑并不重要,这里已提前准备好了一份演示代码,可以结合下面的步骤实际操作。代码本身比较简单,需要特别说明的是,为了能够重复部署,代码引入了SpringBootActuator支持调用API退出服务器进程。步骤一准备构建计划在左侧菜单栏选择构建计划,在打开的页面中点击新建构建计划配置。ci-empty为

  • FrameBot:DNA-蛋白序列纠错工具

    将DNA序列转换为蛋白质序列时,插入和缺失会导致移码(frameshifts)。FrameBot可以检测并纠正这些移码。给定一个queryDNA和一组已知的蛋白质序列,FrameBot将每条蛋白质序列和DNA序列在正反两个方向进行比对,并生成经过校正的蛋白质和DNA序列,以及最佳的全局-局部蛋白质成对比对(global-localproteinpairwisealignment)。当queryDNA和蛋白序列相似度越高时(至少50%),FrameBot准确度越高。FrameBot已经被在一些重要的功能基因中测试过,如:nitrogenasereductase(nifH)butyryl-CoAtransferase(but)butyratekinase(buk)dioxin/dibenzofurandioxygenase(dxnA/dbfA1)dibenzofurandioxygenase(dbfA2)carbazoledioxygenase(carA)cytochromeP-450(p450)alkanehydroxylaseB(alkb)biphenyldioxygenase(bph

  • Java框架-MyBatis三剑客之MyBatis Generator(mybatis-generator MBG插件)详解

    生成器设计思路:连接数据库->获取表结构->生成文件1下载与安装官网文档入口 最方便的maven插件使用方式 贴至pom文件 2新建配置文件填充配置信息(官网示例) 项目实例<?xmlversion="1.0"encoding="UTF-8"?> <!DOCTYPEgeneratorConfiguration PUBLIC"-//mybatis.org//DTDMyBatisGeneratorConfiguration1.0//EN" "http://mybatis.org/dtd/mybatis-generator-config_1_0.dtd"> <generatorConfiguration> <classPathEntrylocation="/Volumes/doc/jar/mysql-connector-java-8.0.18.jar"/> <contextid="DB2Tables"ta

  • K8S 生态周报| Helm v3.2.1 发布

    「K8S生态周报」内容主要包含我所接触到的K8S生态相关的每周值得推荐的一些信息。欢迎订阅知乎专栏「k8s生态」(https://zhuanlan.zhihu.com/container)。1Helmv3.2.1版本发布本周Helm发布了v3.2.1版本,这是v3.2系列的第一个patch版本。此次包含一些值得关注的内容:#7959(https://github.com/helm/helm/pull/7959)修复了一个Helmv3从3.0-rc版一直存在的一个bug,详情见#6899(https://github.com/helm/helm/issues/6899),但--reuse-values这个参数用的人可能不多,实际上影响没那么大; #7653(https://github.com/helm/helm/pull/7653)修改了helmupgrade的行为,允许对一个失败的Release执行helmupgrade进行重新部署,而不需要先删除掉旧的Release;(方便了很多!) 其实本周Helm还发布了v2.16.7,虽然Helm2已经进入了维护期,但不得不说,维护团队还是

  • [689]设置debian的静态IP

    ipconfig-all可查看一下信息想要设置网络的信息如下IP地址:10.10.10.155 子网掩码:255.255.255.0 网关:10.10.10.2广播地址:10.10.10.255 DNS:10.10.10.2,114.114.114.114我们需要编辑2个文件/etc/network/interfaces(配置IP和网关) /etc/resolv.conf(配置DNS服务器)查看可用网卡root@debian:~#ipaddr 1:lo:<LOOPBACK,UP,LOWER_UP>mtu65536qdiscnoqueuestateUNKNOWNgroupdefaultqlen1000 link/loopback00:00:00:00:00:00brd00:00:00:00:00:00 inet127.0.0.1/8scopehostlo valid_lftforeverpreferred_lftforever inet6::1/128scopehost valid_lftforeverpreferred_lftforever 2:ens33:<BROA

  • 数据可视化配色指南:三大配色方法,做出咨询报告一样的图表

    作者MichaelYi,伊瓢编译 量子位出品|公众号QbitAI做数据图表的时候,只会用Excel里的系统默认颜色?别别别,大家都用默认配色,千篇一律,毫无特点。可是学习色彩设计,又是十分费工夫的一件事,不仅要搞明白RGB、CMYK等各种颜色体系,搞懂各种配色方法,重点是还要看大量的案例,培养良好的审美观,防止自己做出来的东西辣眼睛……不如我们来“一文学会”系列吧,这篇MichaelYi发在Medium上的文章,就简单清晰的介绍了三种数据可视化中的配色方法,让你的图表看起来清晰、翔实、用户体验友好,就像咨询公司的报告一样专业。另外,还有不少实用技巧和工具~三种配色方法根据数据的不同类型,有三种不同的调色方法。定性调色板定性调色板主要用在分类展示的数据图中,比如不同国家、不同企业、不同个体分类展示,每个类目没有固定的顺序。当然,你必须得给每个类目一种专属的颜色,不然重复了或者颜色太接近就分不清了。 实在不行可以给同一种颜色调整明度和饱和度,比如红色有暗红色、大红色、粉红色,不过,最好是同一种色系之间有某种联系,比如浅色是以日为单位,深色是以周围单位。或者,用最简单粗暴的方式,把数目太小的

  • NLTK相关知识介绍

    版权声明:本文为博主原创文章,遵循CC4.0BY-SA版权协议,转载请附上原文出处链接和本声明。本文链接:https://blog.csdn.net/github_39655029/article/details/82893018什么是NLTK NLTK,全称NaturalLanguageToolkit,自然语言处理工具包,是NLP研究领域常用的一个Python库,由宾夕法尼亚大学的StevenBird和EdwardLoper在Python的基础上开发的一个模块,至今已有超过十万行的代码。这是一个开源项目,包含数据集、Python模块、教程等;怎样安装 详情可以参见我的另一篇博客NLP的开发环境搭建,通过这篇博客,你将学会Python环境的安装以及NLTK模块的下载;常见模块及用途 NLTK能干啥? 搜索文本单词搜索:相似词搜索;相似关键词识别;词汇分布图;生成文本;计数词汇 #!/usr/bin/envpython #-*-coding:utf-8-*- #@Time:2018-9-2822:21 #@Author:Manu #@Site: #@File:python_base.py

  • LeetCode 31. Next Permutation

    题目c++classSolution{ public: voidnextPermutation(vector<int>&nums){ inttag=0; intz=-1; for(inti=nums.size()-1;i>=0;i--) { if(i!=0&&nums[i]>nums[i-1]) { z=i-1; break; } } if(z==-1){ sort(nums.begin(),nums.end()); return; } for(inti=nums.size()-1;i>=z;i--) { intpos=-1; for(intj=i-1;j>=z;j--) { if(nums[i]>nums[j]) { pos=j; break; } } if(pos!=-1) { swap(nums[i],nums[pos]); sort(nums.begin()+pos+1,nums.end()); break; } } } };复制

  • 工作线程数究竟要设置为多少 | 架构师之路

    一、需求缘起Web-Server通常有个配置,最大工作线程数,后端服务一般也有个配置,工作线程池的线程数量,这个线程数的配置不同的业务架构师有不同的经验值,有些业务设置为CPU核数的2倍,有些业务设置为CPU核数的8倍,有些业务设置为CPU核数的32倍。“工作线程数”的设置依据是什么,到底设置为多少能够最大化CPU性能,是本文要讨论的问题。二、共性认知在进行进一步深入讨论之前,先以提问的方式就一些共性认知达成一致。问:工作线程数是不是设置的越大越好?答:肯定不是的服务器CPU核数有限,能够同时并发的线程数有限,单核CPU设置10000个工作线程没有意义线程切换是有开销的,如果线程切换过于频繁,反而会使性能降低问:调用sleep()函数的时候,线程是否一直占用CPU?答:不占用,等待时会把CPU让出来,给其他需要CPU资源的线程使用。不止sleep()函数,在进行一些阻塞调用时,例如网络编程中的:阻塞accept(),等待客户端连接阻塞recv(),等待下游回包都不占用CPU资源。问:单核CPU,设置多线程有意义么,是否能提高并发性能?答:即使是单核,使用多线程也是有意义的,大多数情况也

  • iOS 上架流程图文详解2022版 (上)

    到了2021年,虽然网上也有大牛写过很多IOSApp上架流程资料,但随着苹果发布机制的微调有些已经过时了。我就趁着这次刚刚发布成功的鲜活经验,记录下来,做一下补充。1、首先得注册AppleDeveloper的开发者账号,最后如果要上架苹果商店,这个账号是要交年费的,核算下来大概600多元人民币。2、接下来要登录AppleDeveloper网站,点击“Account”栏目​3、如果该App需要多人协作开发,请进入People进入人员编辑。注意负责上架AppStore的人员需要有管理级别的权限。​4、人员设置完成过后,进入“Certificates...”页面了。1)先申请证书​2)如果还在开发App,就需要申请下AppleDevelopment证书,里面可以申请开发人员的AppleID以及测试真机如果App额外的敏感功能,比如大部分App都需要的推送,则要申请ApplePushNotifucationserviceSSL(Sandbox&Production)如果需要发布,则要申请iOSDistribution(AppStoreandAdHoc),然后点击下一步"Con

  • mac 下关于node版本的切换

    https://www.jianshu.com/p/10a7547198f5 helloworld!!!

  • 手把手带你使用Paint in 3D和Photon撸一个在线涂鸦画板

    Paintin3D Paintin3D用于在游戏内和编辑器里绘制所有物体。所有功能已经过深度优化,在WebGL、移动端、VR以及更多平台用起来都非常好用! 它支持标准管线,以及LWRP、HDRP和URP。通过使用GPU加速,你的物体将以难以置信的速度被绘制。代码还经过深度优化来防止GC,和将所有绘制操作一起批次完成。 跟贴图系统不同,它是一个纹理绘制解决方案。这意味着你可以绘制你的物体上百万次,还是无帧率丢失,让你创作难以想象的游戏。 它在Unity应用商店上的售价是60美元,地址:https://assetstore.unity.com/packages/tools/painting/paint-in-3d-26286。 Photon Photon中文翻译为“光子”,为有着15年服务器后端开发经验的德国ExitGames公司开发的高效,稳定,可拓展的网络引擎。为目前世界上用户最广泛,支持游戏类型最多的专业网络引擎之一,也是Unity应用商店里用户评价最高的网络组件。 世界多个知名游戏公司和工作室选用Photon作为其产品的网络支持引擎,其中包括WB华纳,Codemaster,2K,G

  • openGL如何在改变窗口大小时,使自己的图形不被拉伸

    这里要注意两个概念:视口和视景体,当视口的纵横比和视景体的纵横比相同的时候,改变窗口大小,图像才不会变形; 视景体是指成像景物所在空间的集合。它是一个空间集合体。 单个的视景体,比如一个球体,若要完全显示,其视景体应该是该球体的最小外接立方体;若要只显示上半部分,则取上半球,其视景体是上半球的最小外接立方体。对于半球而言,上半球是视景体,那么其只有上半球有显示权限,下半球没有,所以就算是将该球体位置拉远,也只能看到上半球。 若视景体仅仅为上半球,那么默认情况下,上半球所映射的画布刚好充满摄像机。将摄像机下移,则摄像机画面中显示的是上半球切面的水平线,水平线以下是黑色背景色。即使此时从理论上来说摄像机对着下半球,但由于视景体仅为上半球,所以下半球是没有显示权限的,是不会被显示的。  对OpenGL而言,视景体就意味着可显示空间,在该空间内的一切物体都可以被显示,都可以被看到,该空间外的一切物体都不能被看到。相机若要看到该空间中的物体,则相机本身就必须处于该视景体空间中。若相机在视景体空间外,哪怕该视景体就在相机正对的面前,相机依然无法看到   例如:控制视口大小为:g

  • Django之分页器组件

    目录Django之分页器组件一Django的分页器(paginator)简介二分页器的简单使用1视图层2模板层三分页器的进阶使用1视图层2模板层 Django之分页器组件 一Django的分页器(paginator)简介 在页面显示分页数据,需要用到Django分页器组件。 -1)项目数据量大了以后,比如涉及到分页,一页一页的加载显示 -2)django中分页器组件,把分页常用的东西,封装到一个类中 -3)实例化得到一个对象,对象里有属性和方法 复制 二分页器的简单使用 #导入分页器的类 fromdjango.core.paginatorimportPaginator ##1Paginator对象的属性和方法 book_list=models.Book.objects.all() #实例化得到对象 #第一个参数:要分页的数据,book_list #第二个参数:每页条数 paginator=Paginator(book_list,10) #Paginator对象的属性和方法 print(paginator.per_page)#每页显示的条数 print(paginator.count)

  • OpenCV函数学习:cvRound,cvFloor,cvCeil

    函数cvRound,cvFloor,cvCeil都是用一种舍入的方法将输入浮点数转换成整数: cvRound返回跟参数最接近的整数值; cvFloor返回不大于参数的最大整数值; cvCeil返回不小于参数的最小整数值。

相关推荐

推荐阅读