对于给定的两个集合,使用哈希表可以在线性时间复杂度内得到他们的交集和并集,具体说明如下:
假设有集合A={1, 7, 5, 13, 9, 10, 11}, B={5, 7, 10, 1, 18, 12},
1)求交集,需要得到结果:A∩B={1, 5, 7,10}
思路如下:
①建立一个哈希表(HashTable),其键(KEY)表示集合中数字的值,其值(VALUE)表示集合中数字出现的次数
②遍历集合A,将集合中的每个数字(KEY)插入哈希表,每个数字的出现次数(VALUE)设置为1
③遍历集合B,对于集合中的每个数字:
如果哈希表中已经存在该数字,将对应的VALUE改为2
如果哈希表中不存在该数字,忽略
④遍历哈希表,输出VALUE为2的数字,即得到A和B的交集
2) 求并集,需要得到结果:AUB={1,5,7,9,10,11,12,13,18}
思路如下:
①建立一个哈希表(HashTable),其键(KEY)表示集合中数字的值,其值(VALUE)可以无视
②遍历集合A,将集合中的每个数字(KEY)插入哈希表
③遍历集合B,对于集合中的每个数字:
如果哈希表中已经存在该数字,忽略
如果哈希表中不存在该数字,将这个数字插入哈希表
④遍历哈希表,输出哈希表中的每个KEY,即为A和B的并集
上面以两个集合为例说明了交集和并集的求法,事实上,上述算法可以很方便的扩展到3个或3个以上的集合
的求交集和求并集。另外求并集时,由于哈希表的值(VALUE)部分不需要用到,所以这个数据结构也可以更换为
哈希集(HashSet)。
分享到:
相关推荐
java代码实现交集,并集 求交集并集叫好用的代码.个人感觉
C++实现字符串求交集、并集、差集
已知两个集合,求这两个集合的交集和并集的MATLAB代码,txt文档
excel取两列数据交集、并集、差集 excel取两列数据交集、并集、差集 excel取两列数据交集、并集、差集
Delphi 两个多边形求交集、并集、差集的源码,使用的是D5,非常古老的版本了,但能解决问题,程序使用标记法,速度非常快,解决了C语言中关于高精度重叠边的问题,示例程序是从CAD中读取多边形数据,方便演示各种...
算法流程: 从数组1的尚未比较的元素中拿出第一个元素array1(i),用array1(i)与array2(j)进行比较(其中j>i且j的长度),可能出现下面两种情况, 1. 数组2中找到了一个与array1(i)相等的元素,则将array2(j)与array...
通过构造模板函数来求集合的交集和并集。 template ,class inputiterator2,class outputiterator> outputiterator my_union(inputiterator1 input1_begin,inputiterator1 input1_end, inputiterator2 input2_begin, ...
用线性表实现集合的求交集和并集的运算 (*^__^*)
C++ stl set 求集合的交集并集差集 编译环境为dev C++
求java数组的交集,并集,差集 实现方法简单但很实用
实现多个数组的数据过滤,最后用一个数组保存数据,实质上就是过滤集合数组,最后得出一个交集。最后返回一个数组。
AutoJs源码-交集_并集_差集_去重(1)。本资源购买前提醒:本源码都是实际autojs项目模板,安装好autojs直接运行即可打开。1、支持低版本autojs。2、资源仅供学习与参考,请勿用于商业用途,否则产生的一切后果将由您...
matlab 中连续区间进行交并集操作,输入输出为向量表示的连续区间如A=[a,b,c,d]表示A=(a,b)U(c,d),A为最简表达式,各个集合不相交
利用指针来实现动态数组,求两个集合的交集和并集。(要求用动态数组来实现)依次分别输入数组A、B长度,并输入A,B中元素,即可得到交集并集
其中应用了链表的复制方法,实现连个链表之间的交集贺并集操作。
c++程序设计实现集合交集并集差集.pdf
用C#简单实现了对字符串数组求交集并集,定义类
是关于两个线性表的合并也就是并集 还有交集
中职数学基础模块交集和并集PPT课件.pptx
1.有序顺序表的元素按照从小到大有序存储; 2.实现有序顺序表的类模板,它的操作如下: ...3.用有序顺序表表示集合,实现两个有序顺序表的并和交(并和交仍是有序顺序表)并分析它们的时间复杂度;