问题

给定一个字符串的集合，格式如：
{{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表+并查集
###########
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}， {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数组合并集合即可。