染色法求解“微信群覆盖”

灰太狼 2021-11-11 16:01 277阅读 0赞

出处：[染色法求解“微信群覆盖”][Link 1]

微信有很多群，现进行如下抽象：

(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年校招笔试题。*

前文《[暴力法求解“微信群覆盖”][Link 2]》，通过以下四个步骤，实施了求解：

(1) **先初始化M个集合**，用集合来表示微信群gid与用户uid的关系；

(2) 找到哪**两个集合需要合并**；

(3) 对有重复元素的集合，进行**集合合并**；

(4) 迭代步骤二和步骤三，**遍历所有集合对**，有相同元素的持续合并，直到算法结束；

但总的来说，暴力法效率非常低，《[暴力法求解“微信群覆盖”][Link 2]》同时提出了几个优化方向，今天重点讨论第一个优化方向：**能不能一次合并多个集合？**

暴力法中，判断两个集合set<i>和set<j>是否需要合并，思路是：遍历set<i>中的所有element，看在set<j>中是否存在，如果存在，说明存在交集，则需要合并。

**哪些集合能够一次性合并？**

当某些集合中包含同一个元素时，可以一次性合并。

**怎么一次性发现，哪些集合包含同一个元素，并合并去重呢？**

回顾一下工作中的类似需求：

M个文件，每个文件包含N个用户名，或者N个手机号，**如何合并去重？**

最常见的玩法是：

cat file\_1 file\_2 … file\_M | sort | uniq > result

**这里的思路是什么？**

(1) 把M\*N个用户名/手机号输出；

(2) sort排序，**排序之后相同的元素会相邻**；

(3) uniq去重，相邻元素如果相同只保留一个；

“排序之后相同的元素会相邻”，就是一次性找出所有可合并集合的关键，这是**染色法**的核心。

举一个**栗子**：

假设有6个微信群，每个微信群有若干个用户：

s1=\{1,0,5\} s2=\{3,1\} s3=\{2,9\}

s4=\{4,6\} s5=\{4,7\} s6=\{1,8\}

假设使用树形set来表示集合。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3d1aGVueW91eXV5b3V5dQ_size_16_color_FFFFFF_t_70][]

首先，给同一个集合中的所有元素染上相同的颜色，表示来自同一个集合。

![20190806084948837.jpg][]

然后，对所有的元素进行排序，会发现：

*  相同的元素一定相邻，并且一定来自不同的集合
 *  同一个颜色的元素被打散了

![20190806084958421.jpg][]

这些相邻且相同的元素，来自哪一个集合，这些集合就是需要合并的，如上图：

*  粉色的1来自集合s1，紫色的1来自集合s2，黄色的1来自集合s6，所以s1s2s6需要合并
 *  蓝色的4来自集合s4，青色的4来自集合s5，所以s4s5需要合并

不用像暴力法遍历所有的集合对，而是一个排序动作，就能找到所有需要合并的集合。

*画外音：暴力法一次处理2个集合，染色法一次可以合并N个集合。*

![20190806085007742.jpg][]

集合合并的过程，可以想象为，相同相邻元素所在集合，染成第一个元素的颜色：

*  紫色和黄色，染成粉色
 *  青色，染成蓝色

最终，剩余三种颜色，也就是三个集合：

s1=\{0,1,3,5,8\}

s3=\{2,9\}

s4=\{4,6,7\}

**神奇不神奇！！！**

染色法有意思么？但仍有**两个遗留问题**：

(1) 粉色1，紫色1，黄色1，三个元素如何找到这三个元素所在的集合s1s2s6呢？

(2) s1s2s6三个集合如何快速合并？

*画外音：假设总元素个数n=M\*N，如果使用树形set，合并的复杂度为O(n\*lg(n))，即O(M\*N\*lg(M\*N))。*

或许有朋友会问，**怎么来排序？**

《[拜托，面试别再问我基数排序了！][Link 3]》

《[拜托，面试别再问我计数排序了！][Link 4]》

《[拜托，面试别再问我桶排序了！][Link 5]》

之前介绍了三种，时间复杂度是线性的排序算法。本例中，**基数排序**和**桶排序**都是非常不错的选择。

还是那句话，**思路比结论更重要**，进一步的优化，且听下回分解。

[Link 1]: https://mp.weixin.qq.com/s/ZFAH_aNMwB4vOuT0b-yilA
[Link 2]: http://mp.weixin.qq.com/s?__biz=MjM5ODYxMDA5OQ==&mid=2651961740&idx=1&sn=3a1b53114f1eaa12e13b5b54df331370&chksm=bd2d0c508a5a854639f0fa035ef844c5a23238e0de6bfa511ef9f4696cf5d60af6f35edd9964&scene=21#wechat_redirect
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3d1aGVueW91eXV5b3V5dQ_size_16_color_FFFFFF_t_70]: /images/20211109/2bdd8736509f44e1afda5f15061cbccd.png
[20190806084948837.jpg]: /images/20211109/0babd38fdd9f40f2a27961fd8cc0ca00.png
[20190806084958421.jpg]: /images/20211109/0a571e0356bc4b6eabe8cdaaf9ca1aca.png
[20190806085007742.jpg]: /images/20211109/20fb1df169a64cdd80deed8b2b508b27.png
[Link 3]: http://mp.weixin.qq.com/s?__biz=MjM5ODYxMDA5OQ==&mid=2651961634&idx=1&sn=1e9617d6f6bd2790eabedca22ea49879&chksm=bd2d0cfe8a5a85e8dd52dd0453abe7118932f3dd0068682c6829c37d69e197acfe0efff051e7&scene=21#wechat_redirect
[Link 4]: http://mp.weixin.qq.com/s?__biz=MjM5ODYxMDA5OQ==&mid=2651961665&idx=1&sn=b7a6d0ca45a0b91801778baec0f759c6&chksm=bd2d0c9d8a5a858b0fc54dbc08d75ecdb4f11383a97222aede422c9f72a7c0240d82e5833aec&scene=21#wechat_redirect
[Link 5]: http://mp.weixin.qq.com/s?__biz=MjM5ODYxMDA5OQ==&mid=2651961685&idx=1&sn=6a5283e79efbb29b57309b870ac3645e&chksm=bd2d0c898a5a859f9236cf0ca766758575541ab594a2bd4151f5de1621bd5c7424b0139889fd&scene=21#wechat_redirect