这是一篇讲算法的文章，从一个面试小题开始，扩展到一系列基础算法，包括几个部分：（一）题目介绍；(2)思路一：暴力法；(3)思路二：着色法；(4)思路三：链表法；(5)思路四：并查法。除了谈论计划，重点分享思考过程。文章较长，可以提前收藏。Part1：题目介绍问题：求微信群覆盖微信有很多群，抽象如下：（1）每个微信群由唯一的gid标识；(2)微信群中的每个用户都有一个唯一的uidID；(3)一个用户可以加入多个群组；(4)一个组可以抽象成一个由不重复的uid组成的集合，例如：g1{u1,u2,u3}g2{u1,u4,u5}可以看出，用户u1加入了两个组g1和g2。画外音：gid和uid都是uint64；集合中没有重复的元素；假设微信有M个群（M为亿级），每个群平均有N个用户（N为十级）。现在需要进行如下操作：(1)如果两个微信群中有相同的用户，合并两个微信群，生成一个新的微信群；比如上面的g1和g2会合并成一个新的组：g3{u1,u2,u3,u4,u5}；画外音：集合g1包含u1，集合g2包含u1，合并后的微信群g3也只包含一个u1。(2)继续进行上述操作，直到所有剩余的微信群中都没有相同的用户为止；以上操作称为：求组覆盖。设计算法，找到群的覆盖，并说明算法的时间和空间复杂度。画外音：你遇到过类似的面试题吗？对于一个复杂的问题，思路一定是“先解决，再优化”。大多数人都不是神，很难一步解决。先用一个比较“笨”的方法来解决，然后再看“笨方法”的痛点，对每个痛点进行优化，不断升级解决方案。第二部分：暴力法当你拿到这道题的时候，很容易想到思路：（1）先初始化M个集合，用集合来表示微信群gid和用户uid的关系；(2)找出哪两个(which)Sets需要合并；(3)接下来，合并集合；(4)迭代步骤2和步骤3，直到所有集合都不存在相同的元素，算法结束；第一步，如何初始化集合？set这个数据结构，大家用的比较多，表示集合：（1）创建M个集合，表示M个微信群gid；(2)在每个集合中插入N个元素，代表微信群中的用户uid；set有两种最常见的实现方式，一种是树集合，一种是哈希集合。假设有一个集合：s={7,2,0,14,4,12}树型集合的实现如下：其特点是：插入和查找的平均时间复杂度为O(lg(n));顺序搜索；节省空间；hash-typeset实现如下：其特点是：插入和查找的平均时间复杂度为O(1)；无法实现有序搜索；画外音：求组覆盖，hash类型实现的初始化效率更高Fast，复杂度为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)中的所有元素；画外音：这一步的时间复杂度是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);}第一行(1)遍历集合set(i)中的第一个Allelements元素;画外音：这一步的时间复杂度是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)//合并画外音：实际复杂度比这个高。随着集合的合并，集合中的元素会越来越多，权重判断和合并的代价会越来越高。第三部分：上色法一般来说，蛮力法是很低效的。集合是一个一个合并的，合并过程中要遍历多次相同的元素。很容易想到一个优化点，一次可以合并多套吗？暴力法中，判断两个集合set和set是否需要合并，思路是：遍历集合中的所有元素，看集合中是否存在，如果存在，则表示有交集，需要合并。哪些集合可以一次合并？当一些集合包含相同的元素时，可以一次合并它们。如何一次找出哪些集合包含相同的元素，并对其进行合并和去重？复习一下工作中的类似需求：M个文件，每个文件包含N个用户名，或者N个手机号，如何合并去重？最常见的玩法是：catfile_1file_2...file_M|sort|uniq>result这里的idea是什么？(1)输出M*N个用户名/手机号；(2)排序，排序后相同的元素相邻；(3)uniq去重，如果相邻的元素相同，则只保留一个；“排序后相同元素相邻”是一次找到所有可合并集合的关键，这也是着色法的核心。举个栗子：假设有6个微信群，每个微信群有几个用户：s1={1,0,5}s2={3,1}s3={2,9}s4={4,6}s5={4,7}s6={1,8}假设用树集来表示集合。首先，同一个集合中的所有元素都被涂上相同的颜色，表明它们来自同一个集合。然后，对所有元素进行排序，你会发现：（1）相同的元素必须是相邻的，并且必须来自不同的集合；(2)相同颜色的元素散落；这些相邻且相同的元素，来自哪个集合，需要合并这些集合，如上图所示：（1）粉色1来自集合s1，紫色1来自集合s2，黄色1来自来自集合s6，所以需要合并s1s2s6；(2)蓝色4来自集合s4，青色4来自集合s5，所以需要合并s4s5；不是像蛮力法那样遍历所有集合对，而是一个排序动作，找到所有需要合并的集合。画外音：暴力法一次处理2组，涂色法一次可以合并N组。合并集合的过程可以想象为相同相邻元素的集合被染成第一个元素的颜色：(1)紫色和黄色，染成粉红色；(2)青色，染成蓝色；最后，剩下的三种颜色，也就是三组：s1={0,1,3,5,8}s3={2,9}s4={4,6,7}魔法不魔法！！！上色方式有趣吗？但是还剩下两个问题：（1）pink1、purple1、yellow1这三个元素如何找到这三个元素所在的集合s1s2s6？(2)三个集合s1s2s6如何快速合并？画外音：假设总元素个数n=M*N，如果使用树集合，合并的复杂度为O(n*lg(n))，即O(M*N*lg(M*N))).让我们继续阅读。Part4:链表法和着色法留下了两个问题：在第（2）步中，如何通过元素快速定位集合？在第（3）步中，如何快速合并集合？下面继续说说这两个问题的优化思路。问题一：如何通过元素快速定位一个集合？普通集合只能通过集合根（root）定位元素，不能通过元素反向定位根。如何支持按元素反向定位根？很容易想到每个节点添加一个parent指针就可以了。更具体的：element{intdata;element*left;element*right;}升级为：element{element*parent;//指向父节点intdata;element*left;element*right;}如上图：所有节点的parents都指向其上级，但只有root->parent=NULL。对于任何一个元素，寻找root的过程是：element*X_find_set_root(element*x){element*temp=x;while(temp->parent!=NULL){temptemp=temp->parent;}returntemp;}很easy发现从元素中找到集合的根的时间复杂度是树的高度，即O(lg(n))。有没有更快的方法？进一步思考，为什么每个节点都指向父节点，有没有可能直接指向根节点呢？更具体地说：element{intdata;element*left;element*right;}升级为：element{element*root;//指向集合根intdata;element*left;element*right;}如上图：所有节点的父节点都是指向集合根的点。对于任意一个元素，求根的过程为：element*X_find_set_root(element*x){returnx->root;}不难发现升级后，从元素中求集合根的时间复杂度为O(1).画外音：不能再快了。另外，这个方法可以在O(1)时间内判断两个元素是否在同一个集合中：boolin_the_same_set(element*a,element*b){return(a->root==b->root);}非常方便的。画外音：两个元素具有相同的根并且在同一个集合中。问题二：如何快速合并集合？暴力法中提到，集合合并的伪代码为：merge(set(i),set(j)){foreach(elementinset(i))set(j).insert(element);}插入一个元素从一个集合到另一个集合。假设set(i)中的元素个数为n1，set(j)中的元素个数为n2，其时间复杂度为O(n1*lg(n2))。在“微信群覆盖”的业务场景中，随着集合的不断合并，集合的高度会越来越高，合并也会越来越慢。有没有更快的方法来合并集合？仔细回顾一下：（1）树形集的优点是支持有序查找，节省空间；(2)hash类型集合的优点是可以快速插入和查找；而“微信群覆盖”场景中对集合的频繁操作是：（1）按元素集合根查找；(2)集合合并；那么，为什么要用树结构或散列结构来表示一个集合呢？画外音：优势完全没有发挥出来。我们来看看，在这个场景下，如果集合用链表来表示会怎么样，合并会不会更快一些？s1={7,3,1,4}s2={1,6}如上图所示，用链表表示这两个集合。可以看出，为了满足“通过元素快速定位集合根”的需求，每个元素还是会指向根。如果要合并s1和s2，需要做两件事：集合1的尾部，链接到集合2的头部（蓝线1）；集合2的所有元素，指向集合1的根（蓝线2,3）；merge最终的效果是：变成了一个更大的集合。假设set(1)中的元素个数为n1，set(2)中的元素个数为n2，则整个合并过程的时间复杂度为O(n2)。画外音：更改set(2)中的元素所花费的时间。哎，我们发现：（1）将短链表连接到长链表；(2)将长链表连接到短链表；使用的时间不同。为了让时间更快，总是使用更快的方法：“元素少的链表”主动连接到“元素多的链表”的尾部。这样，改变的元素数量可以更少，这种优化称为“加权合并”。对于M个微信群，平均每个微信群有N个用户，集合用链表表示，按照“加权合并”的方式合并集合。在最坏的情况下，时间复杂度是O(M*N)。画外音：假设所有集合总共需要合并M次，每次需要改变N个元素的根方向，所以是O(M*N)。因此，针对“M组，每组N个用户，微信群覆盖”的问题，使用“着色法”加“链表法”，核心思想是三步：（1）对所有元素进行全局排序;(2)全局排序后，不同集合中的相同元素必须相邻，通过相同相邻元素一次性找到所有需要合并的集合；(3)合并这些集合，算法完成；其中：步骤(1)，全局排序，时间复杂度O(M*N)；步骤(2)，染色思路，可以快速定位到哪些集合需要合并，为每个元素添加一个属性指向集合根，实现O(1)级元素定位集合；步骤(3)，用一个链表表示集合，用加权合并的方法对集合进行合并。合并的时间复杂度也是O(M*N)；总时间复杂度为：O(M*N)//排序+O(1)//从元素中找出需要合并的集合*O(M*N)//集合合并是不是神奇！！！魔法不止一种，还有别的办法吗？我们往下看。PartV:Disjointset是一个经典的数据结构，它有三种操作：Make-set(a)：生成一个只有一个元素a的集合；Union(X,Y)：合并两个集合X和Y；Find-set(a)：查找元素a所在的集合，即通过元素查找集合；这种数据结构特别适用于解决此类集合的合并和搜索问题，也称为合并搜索集合。能否用来解决“微信群覆盖”问题？1、组合查找的链表，基本都是在链表法中讨论的。为了保证知识的系统性，这里稍微复习一下。如上图所示，联合查找可以用链表来实现。链表实现的联合搜索集中Find-set(a)的时间复杂度是多少？集合中的每一个元素都指向“集合的句柄”，这样就可以“找到元素a所在的集合S”，即Find-set(a)操作在O(1)内完成时间。链表实现的union(X,Y)的时间复杂度是多少？假设有集合：S1={7,3,1,4}S2={1,6}合并S1和S2两个集合，需要做两件事：（1）第一个集合的尾元素，链接到第二个集合的头部元素（蓝线1）；(2)第二个集合的所有元素，指向第一个集合的句柄（蓝线2,3）；合并的效果是：变成了一个更大的集合S1。合并集合时，将短链表连接到长链表，这样改变的元素更少。这种优化称为“加权合并”。画外音：在实现过程中，集合句柄需要存储元素个数、头元素、尾元素等属性，方便上面的操作。假设每个集合的平均元素个数为n，则Union(X,Y)运算的时间复杂度为O(n)。Find-set(a)和Union(X,Y)能否在O(1)时间内完成？是的，这就引出了联合查找的第二种实现方式。2.什么是有根树，有根树和普通树有什么区别？常用的集合是用普通的二叉树实现的。其元素的数据结构为：element{intdata;element*left;element*right;}通过左指针和右指针，父节点指向子节点。对于有根树，其元素的数据结构为：element{intdata;element*parent;}通过子节点指向父节点。假设有一个集合：S1={7,3,1,4}S2={1,6}如果用有根树表示，可能是这样的：所有元素都通过父指针指向集合句柄，并且所有元素Find-set(a)的时间复杂度也是O(1)。画外音：假设集合的第一个元素代表集合句柄。有根树实现union(X,Y)的过程是怎样的？时间复杂度是多少？联合搜索是通过有根树实现的。合并集合时，只需将一个集合句柄指向另一个集合即可。如上图，S2的句柄指向S1的句柄，集合合并完成：S2死了，S1变成了更大的集合。很容易知道集合合并的时间复杂度是O(1)。会发现集合合并后，有根树的高度变高了，类似于“加权合并”的优化思路。节点数少的有根树总是指向节点数多的有根树（更准确的说，是高度矮的树，指向高度高的树），这种优化称为“按等级合并”。新问题来了。集合合并后，并不是所有元素的所有Find-set(a)操作都是O(1)。我应该怎么办？如S1和S2合并后的新S1所示，第一次“通过元素6找到新S1的句柄”，O(1)时间无法完成，需要两次操作。但是，为了让以后的“通过元素6找到新S1的句柄”的操作能够在O(1)时间内完成，在第一次执行Find-set("6")时，需要到元素6的“寻根”路径上面的所有元素都指向集合句柄，如下图所示。如果某个元素不直接指向集合句柄，那么在第一次Find-set(a)操作时，路径上的所有元素都会直接指向集合句柄。这种优化称为“路径压缩”。画外音：当路径上的元素第二次执行Find-set(a)时，时间复杂度为O(1)。实施“路径压缩”优化后，Find-set的平均时间复杂度仍然是O(1)。总结一下。通过链表实现查找：(1)Find-set的时间复杂度为O(1)常数时间；(2)Union的时间复杂度是集合中元素的平均个数，即线性时间；画外音：别忘了优化的“加权合并”。通过有根树实现联合搜索：(1)联合的时间复杂度为O(1)常数时间；(2)Find-set的时间复杂度通过"mergebyrank"和"pathcompression"优化，平均时间复杂度也是O(1)；也就是说，使用联合搜索非常适合解决“微信群覆盖”的问题。知其然，知其所以然，想法往往比结果更重要。算法其实挺有意思的。【本文为专栏作者《58神剑》原创稿件，转载请联系原作者】点此阅读更多该作者好文
