本文主要是介绍“微信群覆盖”，线性求解方案？，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目：求微信群覆盖
微信有很多群，现进行如下抽象：
(1) 每个微信群由一个唯一的gid标识；
(2) 微信群内每个用户由一个唯一的uid标识；
(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) 不断的进行上述操作，直到剩下所有的微信群都不含相同的用户为止；
将上述操作称：求群的覆盖。
设计算法，求群的覆盖，并说明算法时间与空间复杂度。
画外音：58同城2013年校招笔试题。
《暴力法求解“微信群覆盖”》使用了暴力法，循环遍历所有的集合对，合并存在公共元素的集合对，暴力求解。
《染色法求解“微信群覆盖”》使用了染色法，通过以下几个步骤，加快了求解速度：
(1) 全部元素全局排序；
(2) 全局排序后，不同集合中的相同元素，一定是相邻的，通过相同相邻的元素，一次性找到所有需要合并的集合；
(3) 合并这些集合，算法完成；
同时文章遗留了两个问题：
步骤(2)中，如何通过元素快速定位集合？
步骤(3)中，如何快速合并集合？
今天，将要讲讲这两个问题的优化思路。
问题一：如何由元素快速定位集合？
普通的集合，只能由集合根(root)定位元素，不能由元素逆向定位root，如何支持元素逆向定位root呢？
很容易想到，每个节点增加一个父指针即可。
更具体的：
element{
int data;
element* left;
element* right;
}
升级为：
element{
element* parent; // 指向父节点
int data;
element* left;
element* right;
}
如上图：所有节点的parent都指向它的上级，而只有root->parent=NULL。
对于任意一个元素，找root的过程为：
element* X_find_set_root(element* x){
element* temp=x;
while(temp->parent != NULL){
temp= temp->parent;
}
return temp;
}
很容易发现，由元素找集合根的时间复杂度是树的高度，即O(lg(n))。
有没有更快的方法呢？
进一步思考，为什么每个节点要指向父节点，直接指向根节点是不是也可以。
更具体的：
element{
int data;
element* left;
element* right;
}
升级为：
element{
element* root; // 指向集合根
int data;
element* left;
element* right;
}
如上图：所有节点的parent都指向集合的根。
对于任意一个元素，找root的过程为：
element* X_find_set_root(element* x){
return x->root;
}
很容易发现，升级后，由元素找集合根的时间复杂度是O(1)。
画外音：不能更快了吧。
另外，这种方式，能在O(1)的时间内，判断两个元素是否在同一个集合内：
bool in_the_same_set(element* a, element* b){
return (a->root == b->root);
}
甚为方便。
问题二：如何快速进行集合合并？
《暴力法求解“微信群覆盖”》一文中提到过，集合合并的伪代码为：
merge(set(i), set(j)){
foreach(element in set(i))
set(j).insert(element);
}
把一个集合中的元素插入到另一个集合中即可。
假设set(i)的元素个数为n1，set(j)的元素个数为n2，其时间复杂度为O(n1*lg(n2))。
在“微信群覆盖”这个业务场景下，随着集合的不断合并，集合高度越来越高，合并会越来越慢，有没有更快的集合合并方式呢？
仔细回顾一下：
树形set的优点是，支持有序查找，省空间
哈希型set的优点是，快速插入与查找
而“微信群覆盖”场景对集合的频繁操作是：
由元素找集合根
集合合并
那么，为什么要用树形结构或者哈希型结构来表示集合呢？
画外音：优点完全没有利用上嘛。
让我们来看看，这个场景中，如果用链表来表示集合会怎么样，合并会不会更快？
s1={7,3,1,4}
s2={1,6}
如上图，分别用链表来表示这两个集合。可以看到，为了满足“快速由元素定位集合根”的需求，每个元素仍然会指向根。
s1和s2如果要合并，需要做两件事：
(1) 集合1的尾巴，链向集合2的头(蓝线1)；
(2) 集合2的所有元素，指向集合1的根(蓝线2,3)；
合并完的效果是：
变成了一个更大的集合。
假设set(1)的元素个数为n1，set(2)的元素个数为n2，整个合并的过程的时间复杂度是O(n2)。
画外音：时间耗在set(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) //集合合并
希望大家有收获。
这几篇文章是在讲解决问题的思路，是希望大家从思路中得到启示，如果阅读完文字，能引发一些思考，能有一些收获，就是好的。是不是“并查集”真的这么重要么？
思路比结论重要，有收获就是好的。
下一篇介绍“并查集”。
架构师之路-分享可落地的技术文章
相关推荐：
《暴力法求解“微信群覆盖”》
《染色法求解“微信群覆盖”》
这篇关于“微信群覆盖”，线性求解方案？的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
