精华内容
下载资源
问答
  • 2012-09-17 20:22:35

    给定一个字符串的集合,格式如: 
    {aaa  bbb  ccc}, {bbb   ddd},{eee   fff},{ggg},{ddd   hhh} 
    要求将其中交集不为空的集合合并,要求合并完成后的集合之间无交集,例如上例应

    输出 
    {aaa  bbb  ccc  ddd  hhh},{eee   fff}, {ggg} 
    (1)请描述你解决这个问题的思路; 
    (2)请给出主要的处理流程,算法,以及算法的复杂度 
    (3)请描述可能的改进(改进的方向如效果,性能等等,这是一个开放问题)。


    我查了查网上的解法,只看到一个(参见http://blog.csdn.net/lillllllll/article/details/4162605),我有一点新想法,说明如下:

    1. 首先得到所有元素的集合(aaa, bbb, ccc, ddd, eee, fff, ggg, hhh),复杂度O(N),N是所有元素的个数;

    2. 为所有集合标记一个二进制数,来表示包含哪些集合,得到数组int bina[5]复杂度O(N^2);

        如题,{aaa, bbb, ccc} = 1 1 1 0 0 0 0 0,

                    {bbb, ddd}         = 0 1 0 1 0 0 0 0,

                    {eee, fff}             = 0 0 0 0 1 1 0 0,

                    {ggg}                  = 0 0 0 0 0 0 1 0,

                    {ddd, hhh}         = 0 0 0 1 0 0 0 1,

    3. 然后写一个函数,判断int数组中的第一个元素是否与其他元素&操作为空,复杂度为O(M),M是原集合的个数

        a. 为空则输出该元素对应的集合,并删除第一个元素,递归调用本方法;

        b. 不为空则与那个元素做或操作合并,删除那个元素,递归调用本方法;

        c. 如果只剩下一个元素则输出其对应的字符串;

    4. 所有的结合已经得到了。

    从上面的复杂度看,应该是比原来网上的方法好一些,欢迎大家踊跃拍砖!

    更多相关内容
  • 合并有交集集合

    千次阅读 2019-02-15 16:08:48
    要求将其中交集不为空的集合合并,要求合并完成后的集合之间无交集,例如上例应 输出 {{a,b,c,d,h},{e,f}, {g}} 工作一年第一次遇到到的相对比较难的算法题, 看了网上的思路, 然后自己实现了下 思路 初始化一个值...

    问题

    给定一个字符串的集合,格式如:
    {{a,b,c}, {b,d},{e,f},{g},{d,h}}
    要求将其中交集不为空的集合合并,要求合并完成后的集合之间无交集,例如上例应

    输出
    {{a,b,c,d,h},{e,f}, {g}}

    工作一年第一次遇到到的相对比较难的算法题, 看了网上的思路, 然后自己实现了下

    思路

    初始化一个值全为-1, 大小跟给定的字符串集合大小一样的数组(下文叫定位数组)。然后把所有字符串转换成这种形式(字符串和字符串所出现在的集合的索引) 下文叫索引数组的集合

    a	0
    b	0,1
    c	0
    d	1,4
    e	2
    f	2
    g	3
    h	4
    

    先对索引数组的集合进行排序(没有排序会影响结果), 然后循环索引数组的集合操作定位数组( 如果索引数组大小为1, 且定位数组的当前值的位置的值为-1, 则在定位数组的当前值的位置插入当前值, 如果当前值位置的值不为-1, 则不做操作;如果索引数组有多个元素, 则依次循环每个索引,找到索引数组在定位数组里面的最小值插入

    a	0				[  0, -1, -1, -1, -1] 
    c	0				[  0, -1, -1, -1, -1]
    b	0,1				[  0,  0, -1, -1, -1] 
    d	1,4				[  0,  0, -1, -1,  0]
    e	2				[  0,  0,  2, -1,  0]
    f	2				[  0,  0,  2, -1,  0]
    g	3				[  0,  0,  2,  3,  0]
    h	4				[  0,  0,  2,  3,  0]
    

    最后这个结果数组 [0, 0, 2, 3, 0] 就是我们想要的

    • 位置为 0,1,4 为一组,所以 {a,b,c},{b,d},{d,h} 是一组。
    • 位置 2 一组, 即 {e,f}
    • 位置 3 一组, 即 {g}

    scala实现

    废话不多说,上代码。这里是用Scala语言实现的

    def fix(): Unit = {
        val data: Array[Set[String]] = Array(
          Set("a", "b", "c")
          , Set("b", "d" )
          , Set("e", "f")
          , Set("g")
          , Set("d", "h")
    
        )
        // 初始化一个跟groupWithSrc一样大小的数组, 全为-1
        val array = List.fill[Int](data.length)(-1).toArray
        val map = mutable.HashMap[String, ArrayBuffer[Int]]()
        for (i <- data.indices) {
          data(i).foreach(s => {
            if (map.containsKey(s)) { // 如果已经存在
              map(s).append(i) // 在原来的基础上增加现在的索引
            } else {
              map.put(s, ArrayBuffer(i))
            }
          })
        }
        val values = map.values
          .toList.sortWith((a, b) => a.mkString("") < b.mkString("")) // 排序
        println(values)
    
        values.foreach(v => {
          val indexs: ArrayBuffer[Int] = v.sortWith((a, b) => a < b)
          indexs.foreach(i => {
            val arrayI = array(i)
            if (indexs.size == 1) {
              if (arrayI == -1) { // 如果index只有一个而且位置为-1则直接插入
                array(i) = i
              }
            } else { // 如果index不止一个
              val indValues = indexs.map(array(_)).filter(_ != -1)
              val min = if (indValues.isEmpty) i else indValues.min  // 找到所有索引位置最小的值, 如果没有就当前值
              if (arrayI == -1) { //如果位置为-1 则直接插入
                array(i) = min
              } else { // 如果位置已经有值, 则比对原值是否比现在值小, 插入小的
                array(i) = if (arrayI < min) arrayI else {
                  values.foreach(arr => {  // 如果有改动, 则所有包含这个索引的都需要改动
                    if (arr.contains(i)){
                      arr.foreach(ei => array(ei) = min)
                    }
                  })
                  min
                }
              }
            }
          })
        })
        val tmap = new mutable.HashMap[Int, ListBuffer[Int]]()
        for (i <- array.indices) {
          val e = array(i)
          if (tmap.containsKey(e)) {
            tmap(e).append(i)
          } else {
            tmap.put(e, ListBuffer(i))
          }
        }
        var newBuffer = new ListBuffer[Set[String]]
        tmap.values.foreach(v => {
          var set: Set[String] = Set()
          v.foreach(set ++= data(_))
          newBuffer.append(set)
        })
    
        println(newBuffer)
    
      }
    

    最后打印结果
    在这里插入图片描述

    注意的点

    1.索引数组的集合一定要排序
    2.如果当前位置有值, 一定要看是否是当前索引数组的最小值, 如果不是要重新插入最小值。
    3.如果有改动, 则所以包含这个索引的都需要改动

    展开全文
  • 这样通过遍历,就建立起了一个并查集结构,将所有有交集的元素指向同一个集合中。 然后建立一个列表,列表下标为集合编号,下标对应元素为并查集的根集合。通过子hash,汇总各集合对应的根集合,并将其更新到列表中...

    方法:hash表+并查集


    建立一个hash表,key为集合元素,value为元素出现的集合,(或者用链表实现也可,因为链表构造比较麻烦所以偷懒了。)同时建立一个子hash,作用是建立当前元素所在集合与元素第一次出现的集合之间的关系,key为元素当前的集合,value为元素第一次出现的集合。这样通过遍历,就建立起了一个并查集结构,将所有有交集的元素指向同一个集合中。
    然后建立一个列表,列表下标为集合编号,下标对应元素为并查集的根集合。通过子hash,汇总各集合对应的根集合,并将其更新到列表中。然后根据列表记录汇总合并对应集合即可。
    注意在子hash中,元素第一次出现的集合可能并非根集合,此时要通过继续查找子hash找到根集合。
    更新一下代码:
    代码如下(python)

    ###########
    #将多个集合合并成没有交集的集合。 hash表+并查集
    ###########
    lista=[['aaa','bbb','ccc'],['bbb','ddd'],['eee','fff'],['ggg'],['ddd','hhh']]
    lenth = len(lista)
    position = [-1 for _ in range(lenth)]
    dict1 = {}
    hash = {}
    res =[]
    for i in range(lenth):
        for j in lista[i]:
            if j not in dict1:#如果元素没有出现过,建立元素与所属集合的键值对
                if i not in hash:#如果所属集合没有出现过。认为所属集合是父集合,建立连接关系
                    hash[i] = i
                    dict1[j] = i
                else:
                    dict1[j] = i
            else:
                temp = dict1[j]#如果元素已经出现过,建立父子集合之间的连接关系
                hash[i] = temp#确保一个集合在同时有未出现过元素和已出现过元素的情况下,能够正确与之前集合建立联系
    temphash = {}
    for i in range(lenth):
        j = i
        while hash[j]!=j:
            j = hash[j]
        position[i] = j#将子集合指向根集合
        if j not in temphash:
            temphash[j] = 1
    for i in range(lenth):
        if position[i]==i:
            continue
        else:
            lista[position[i]].extend(lista[i])#合并集合
            lista[position[i]] = list(set(lista[position[i]]))#合并后去重
    for key in temphash:
        res.append(lista[key])#temphash中存储的都是并查集的父集合(没有上一级的集合),根据temphash生成结果
    print(res)
    '''
    
    展开全文
  • 给定一个字符串的集合,格式如:{aaa bbb ccc}, {bbb ddd},{eee fff},{ggg},{ddd hhh}要求将其中交集不为空的集合合并,要求合并完成后的集合之间无交集,例如上例应输出{aaa bbb ccc ddd hhh},{eee fff}, {...

    题目

    给定一个字符串的集合,格式如:{aaa bbb ccc}, {bbb ddd},{eee fff},{ggg},{ddd hhh}要求将其中交集不为空的集合合并,要求合并完成后的集合之间无交集,例如上例应输出{aaa bbb ccc ddd hhh},{eee fff}, {ggg}。

    思考

    我面试的时候说的是建立邻接矩阵,然后深度遍历的方法,时间复杂度和空间复杂度都是O(n*n),估计面试官也不满意。

    网上找的,相关的解答非常少,最详细,最优复杂度的应该是这个https://www.iteye.com/blog/bylijinnan-1502690,以下的题解是我参考前面的链接,详细描述整个算法过程而写的。

    题解

    大致的做法如下:

    1、首先给每个集合按顺序编号0,1,2,。。。

    0: {aaa bbb ccc} 
    1: {bbb ddd} 
    2: {eee fff} 
    3: {ggg} 
    4: {ddd hhh} 
    

    2、创建一个map,在每个键值对中,key是一个字符串,value是一个链表,链表装的是这个字符串所在的集合里编号(一个字符串可能出现在多个集合中,其对应的链表有多个节点)。为了构建这样的一个map,需要依次遍历所有集合,对于遍历到的每一个字符串,都在它对应的链表里记录下来当前它所在的集合编号。最后map里的键值对如下:

    aaa: 0          
    bbb: 0, 1       
    ccc: 0          
    ddd: 1, 4       
    eee: 2           
    fff: 2          
    ggg: 3          
    hhh: 4          
    

    3、最后就是考虑如何合并集合。首先设置一个长度等于集合个数的int数组,即A[5]。其中A[m]=n;代表把集合m合并到集合n里去。为了构造这个数组 ,需要遍历map中每个键值对。查看当前遍历到的字符串对应的链表里的节点数:

    • 如果链表节点数为1,说明这个字符串只在一个集合里出现过,那么它不会引起集合的合并,直接考虑下一个字符串。
    • 如果链表节点数大于1,说明这个字符串在多个集合里出现过,它会引起集合的合并。此时要做的就是,把链表后面的节点的集合全部合并到第一个节点的集合里去,具体来说就是设置A[后面节点的集合编号]=第一个节点的集合编号

    具体过程如下,记录了每遍历一个键值对后int数组的变化,其中int数组初始化元素全为-1,代表这个集合不需要合并到其他集合里去:

    [-1, -1, -1, -1, -1] 
    aaa: 0          
    [-1, -1, -1, -1, -1] 
    bbb: 0, 1       
    [-1, 0, -1, -1, -1] //使A[1]=0
    ccc: 0          
    [-1, 0, -1, -1, -1] 
    ddd: 1, 4       
    [-1, 0, -1, -1, 0] //使A[4]=1,但是由于A[1]=0,即集合1已经计划合并到0了,所以这里改为A[4]=0
    eee: 2          
    [-1, 0, -1, -1, 0] 
    fff: 2          
    [-1, 0, -1, -1, 0] 
    ggg: 3          
    [-1, 0, -1, -1, 0] 
    hhh: 4          
    [-1, 0, -1, -1, 0] 
    

    可见最后int数组为[-1, 0, -1, -1, 0],说明原本的集合1、4被合并到集合0里去了,合并后总共剩下三个集合0、2、3。

    4、最后按照上面得出的int数组合并集合即可。

    展开全文
  • 1.在平时的时候经常会用到求交集、补集、并集、差集的问题 本文通过引入org.apache.commons.collections4.CollectionUtils 进行很方便的解决 ArrayList arrayList=new ArrayList(); List<String> list =...
  • JAVA List合并集合

    千次阅读 2021-03-04 07:43:39
    import java.util.ArrayList;...public class test {public static void main(String[] args) throws Exception {/*测试合并两个类型相同的list*/List list1 = new ArrayList();List list2 = new ArrayList(...
  • //记录集合合并后的归属 for(i=0; i; i++) if(b[i]!=i) b[i]=b[b[i]]; map, vector*> > m_union; map, vector*> >::iterator m_u_iter; //添加合并后的字符串 for(m_iter=m.begin(); m_iter!=m.end(); ...
  • 将包含x和y的动态集合(比如说Sx和Sy)合并为一个新的集合(即这两个集合的并集),而不是简单的把两个元素合并成一个集合,而是把两个元素所在的集合合并成一个新集合合并两个不相交集合操作很简单: 利用FIND-...
  • 集合合并

    2020-09-11 22:42:35
    将其中交集不为空的集合合并,保证合并完成后所有集合之间无交集,输出合并后的集合个数以及最大集合中元素的个数。 输入描述: 输入格式: 第一行为一个数字N,表示集合数。 接下来N行,每行一个非空集合,包含若干...
  • 1.1交集 两个或者多个集合之间用&符号链接实现,提取共有元素 1.2并集 两个或者多个集合之间用 | 符号连接实现,提取所有元素 二、公共方法 2.1 + 合并意思(字符串,列表,元组) 2.2、* 复制 (字符...
  • js合并交集

    2017-03-31 16:07:00
    /***each是一个集合迭代函数,它接受一个函数作为参数和一组可选的参数<br/>*这个迭代函数依次将集合的每一个元素和可选参数用函数进行计算,并将计算得的结果集返回{%example<script>vara=[1,2,3,4]....
  • 参考了以下三篇博客,在此列出,以表尊重与感谢。 https://juejin.im/post/6844903833726894093 ... 一、集合的交并差 public static void main(String[] args) { List<St
  • 1. 两个set的合并 >>> a = {1,2,3} >>> b = {3,4,5} >>> c = a | b >>> print(c) {1, 2, 3, 4, 5}
  • 可以用于 Java多个集合之间合并及元素比较的简单方法public static void main(String[] args) {Listlist = new ArrayList<>();Listlist2 = new ArrayList<>();list.add("aaa");list.add("李四");list....
  • list集合交集,并集

    千次阅读 2021-04-05 20:37:49
    如果存在两个集合,在java中如何快速的取它们的交集、并集这些操作呢? 1.先给出两个List集合 List listA = new ArrayList(); List listB = new ArrayList(); listA.add(“A”); listA.add(“B”); listB.add(“B”)...
  • Java两个list合并交集

    千次阅读 2015-01-04 17:07:26
    两个List,分别是lsit1和list2,取这两个List的交集 List citylist1 = new ArrayList(); citylist1.add("青岛"); citylist1.add("济南"); citylist1.add("威海"); citylist1.add("日照"); 第一个list含有四个...
  • STL库中丰富的集合运算方法,我们可以使用它们快速完成交集、并集、差集、对称差集的运算。(转载请指明出于breaksoftware的csdn博客) 交集(intersection) 交集集合运算中经常会用到的计算,其表达是两个...
  • java求两个集合交集

    2021-03-06 23:02:40
    一, JAVA 期末测试 期末测试 单选题( 单选题(每题 1 分共 20 分) 题目} 要建立一个线程,可以从下面哪一个...java Java 集合框架——接口 Java 集合框架——接口 接口 集合核心接口(core collection interfaces)包含...
  • **交集:**两个集合相交的部分! 集合1:张三,李四,王五 ,赵六 集合2:田七,赵六,张三 ,阿飞 交集 = 张三,赵六 案例代码: ArrayList<String> datas = new ArrayList<String>(); //向集合中...
  • 如何使用C++实现一个简单的集合类,这篇文章主要介绍了C++简单集合类的实现方法,感兴趣的小伙伴们可以参考一下
  • Java8两个list集合合并成一个list集合

    千次阅读 2021-10-27 11:13:02
    现在以下一个场景:需要将集合 A:{"id": "12345","name": "zhangsan"} B:{"id": "12345", "age": 23} 合并成一个新的集合 C:{"id": "12345","name": "zhangsan", "age": 23} 1、将listA集合转换为map Map...
  • 12 - 集合之间的并集与交集

    千次阅读 2020-02-10 18:09:09
    Python集合操作
  • 简单说一下集合求并集、差集以及交集方法。常用方法就是集合api与jdk8中stream流.下面已案例的形式简单说下使用以及区别. public static void main(String[] args) { ArrayList<Integer> integers = new ...
  • 两个集合具有不同的 key HashMap map1=new HashMap(); map1.put("1", "A"); HashMap map2 = new HashMap(); map2.put("2", "B"); map2.put("3", "C"); map1.putAll(map2); System.out.println(map1); 输出...
  • C# list集合获取并集,交集、差集、联集,同一集合是否重复元素一、Intersect 交集,Except 差集,Union 并集二、比较两个List集合内容是否相同三、判断一个集合里面相同的元素四、获取两个集合中相同的和不同的...
  • //合并操作 void MergeList ( const SqList * A , const SqList * B , SqList * C ) { int i = 0 , j = 0 ; while ( i < A -> length && j < B -> length ) { if ( * GetElem ( A , i...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 31,130
精华内容 12,452
关键字:

合并有交集的集合