Title:微信群覆盖微信有很多群，现在抽象如下：每个微信群用一个***gid标识；微信群中的每个用户都由一个***uid标识；一个用户可以加入多个群组；groups可以抽象成一个由不重复的uid组成的集合，例如：g1{u1,u2,u3}g2{u1,u4,u5}可以看到用户u1加入了两个groupg1和g2。画外音，注意：gid和uid都是uint64；集合中没有重复的元素；假设微信有M个群（M为亿级），每个群平均有N个用户（N为十级）。现在我们需要进行如下操作：(1)如果两个微信群中有相同的用户，合并两个微信群，生成一个新的微信群；比如上面的g1和g2会合并成一个新的组：g3{u1,u2,u3,u4,u5}；画外音：集合g1包含u1，集合g2包含u1，合并后的微信群g3也只包含一个u1。(2)继续进行上述操作，直到所有剩余的微信群中都没有相同的用户为止；以上操作称为：求组覆盖。设计算法，找到群的覆盖，并说明算法的时间和空间复杂度。画外音：58同城2013年校招试题。对于一个复杂的问题，思路一定是“先解决，再优化”。大多数人都不是神，很难一步解决。先用一个比较“笨”的方法来解决，然后再看“笨方法”的痛点，对每个痛点进行优化，不断升级解决方案。拿到这道题，很容易想到思路：先初始化M个集合，用集合来表示微信群gid和用户uid的关系；找到需要合并的两个（哪些）集合；然后，合并集合；迭代步骤2和步骤3，直到所有集合中没有相同的元素，算法结束；第一步，如何初始化集合？set的数据结构被大家广泛使用来表示集合：创建M个集合来表示M个微信群gid，每个集合插入N个元素来表示微信群中的用户uidset。最常见的实现方式有两种，一种是树集，一种是哈希集。假设有一个集合：s={7,2,0,14,4,12}树型集合的实现如下：其特点是：插入和查找的平均时间复杂度为O(lg(n))并且可以有序查找节省空间的hash类型集合的实现如下：其特点是：插入和查找的平均时间复杂度为O(1)无法实现有序查找O(M*N).第二步，如何判断两个（多个）集合是否应该合并？对于set(i)和set(j)，判断其中是否有重复元素。如果是这样，则需要合并它们。判断权重的伪代码为：//判断合并set(i)和set(j)个元素(1)foreach(elementinset(i))(2)if(elementinset(j))merge(set(i),设置(j));***第(1)行遍历第一个集合set(i)中的所有元素element；画外音：这一步的时间复杂度是O(N)。第二行（2）判断元素是否在第二个集合set(j)中；画外音：如果使用哈希类型集合，第二行（2）的平均时间复杂度为O(1)。这一步的时间复杂度至少是O(N)*O(1)=O(N)。第三步，如何合并集合？如果集合对set(i)和set(j)需要合并，只需将一个集合中的元素插入另一个集合：//pairset(i)andset(j)forcollectionmergemerge(set(i),set(j)){(1)foreach(elementinset(i))(2)set(j).insert(element);}***line(1)遍历*第一个集合set(我）;画外音：这一步的时间复杂度是O(N)。第二行（2）将元素插入到集合set(j)中；画外音：如果使用哈希类型集合，第二行（2）的平均时间复杂度为O(1)。这一步的时间复杂度至少是O(N)*O(1)=O(N)。第四步：迭代第二步和第三步，直到结束。对于M集合，对所有集合对使用暴力判断合并重复元素。用两个for循环暴力解决：(1)for(i=1toM)(2)for(j=i+1toM)//判断合并set(i)和set(j)个元素foreach(elementinset(i))if(elementinset(j))merge(set(i),set(j));递归调用，两次for循环，复杂度为O(M*M)。综上所述，如果这样解决组覆盖问题，时间复杂度至少为：O(M*N)//集合初始化的过程+O(M*M)//双for循环递归*O(N)//判断权重*O(N)//合并画外音：实际复杂度比这个高。随着集合的合并，集合中的元素会越来越多，权重判断和合并的代价会越来越高。基于“先求解，再优化”的思路，我的脑海中自然而然地冒出了很多优化方向的问题：（1）能否通过元素快速定位集合？画外音：通过集??合查找元素，哈希类型集合的时间复杂度为O(1)；如何通过元素查找集合（句柄）来实现它？(2)集合可以快速合并吗？(3)一次可以合并多套吗？经典数据结构，不相交集，它有三种操作：Make-set(a)：生成只有一个元素a的集合；Union(X,Y)：合并两个集合X和Y；Find-set(a)：查找元素a所在的集合，即通过元素查找集合；它特别适用于解决此类集合的合并和搜索问题，也称为并集搜索。如何使用组合查询来解决“微信群覆盖”的问题，后面会介绍。画外音：先介绍“合并查找”方案，后面再介绍其他方案。知道联合搜索的思想和原理比知道什么是联合搜索更重要。算法其实挺有意思的。【本文为专栏作者《58神剑》原创稿件，转载请联系原作者】点此阅读更多该作者好文
