求解“微信群覆蓋”的三種方法：暴力，染色，鏈表，并查集
這是一篇聊算法的文章，從一個(gè)小面試題開(kāi)始，擴(kuò)展到一系列基礎(chǔ)算法，包含幾個(gè)部分：
(1) 題目簡(jiǎn)介;
(2) 思路一：暴力法;
(3) 思路二：染色法;
(4) 思路三：鏈表法;
(5) 思路四：并查集法。
除了聊方案，重點(diǎn)分享思考過(guò)程。文章較長(zhǎng)，可提前收藏。
第一部分：題目簡(jiǎn)介
問(wèn)題提出：求微信群覆蓋
微信有很多群，現(xiàn)進(jìn)行如下抽象：
(1) 每個(gè)微信群由一個(gè)唯一的gid標(biāo)識(shí);
(2) 微信群內(nèi)每個(gè)用戶由一個(gè)唯一的uid標(biāo)識(shí);
(3) 一個(gè)用戶可以加入多個(gè)群;
(4) 群可以抽象成一個(gè)由不重復(fù)uid組成的集合，例如：
- g1{u1, u2, u3}
- g2{u1, u4, u5}
可以看到，用戶u1加入了g1與g2兩個(gè)群。
畫(huà)外音：
- gid和uid都是uint64;
- 集合內(nèi)沒(méi)有重復(fù)元素;
假設(shè)微信有M個(gè)群(M為億級(jí)別)，每個(gè)群內(nèi)平均有N個(gè)用戶(N為十級(jí)別).
現(xiàn)在要進(jìn)行如下操作：
(1) 如果兩個(gè)微信群中有相同的用戶，則將兩個(gè)微信群合并，并生成一個(gè)新微信群;
例如，上面的g1和g2就會(huì)合并成新的群：
g3{u1, u2, u3, u4, u5};
畫(huà)外音：集合g1中包含u1，集合g2中包含u1，合并后的微信群g3也只包含一個(gè)u1。
(2) 不斷的進(jìn)行上述操作，直到剩下所有的微信群都不含相同的用戶為止;
將上述操作稱(chēng)：求群的覆蓋。
設(shè)計(jì)算法，求群的覆蓋，并說(shuō)明算法時(shí)間與空間復(fù)雜度。
畫(huà)外音：你遇到過(guò)類(lèi)似的面試題嗎?
對(duì)于一個(gè)復(fù)雜的問(wèn)題，思路肯定是“先解決，再優(yōu)化”，大部分人不是神，很難一步到位。先用一種比較“笨”的方法解決，再看“笨方法”有什么痛點(diǎn)，優(yōu)化各個(gè)痛點(diǎn)，不斷升級(jí)方案。
第二部分：暴力法
拿到這個(gè)問(wèn)題，很容易想到的思路是：
(1) 先初始化M個(gè)集合，用集合來(lái)表示微信群gid與用戶uid的關(guān)系;
(2) 找到哪兩個(gè)(哪些)集合需要合并;
(3) 接著，進(jìn)行集合的合并;
(4) 迭代步驟二和步驟三，直至所有集合都沒(méi)有相同元素，算法結(jié)束;
第一步，如何初始化集合?
set這種數(shù)據(jù)結(jié)構(gòu)，大家用得很多，來(lái)表示集合：
(1) 新建M個(gè)set來(lái)表示M個(gè)微信群gid;
(2) 每個(gè)set插入N個(gè)元素來(lái)表示微信群中的用戶uid;
set有兩種最常見(jiàn)的實(shí)現(xiàn)方式，一種是樹(shù)型set，一種是哈希型set。
假設(shè)有集合：
s={7, 2, 0, 14, 4, 12}
樹(shù)型set的實(shí)現(xiàn)如下：
其特點(diǎn)是：
- 插入和查找的平均時(shí)間復(fù)雜度是O(lg(n));
- 能實(shí)現(xiàn)有序查找;
- 省空間;
哈希型set實(shí)現(xiàn)如下：
其特點(diǎn)是：
- 插入和查找的平均時(shí)間復(fù)雜度是O(1);
- 不能實(shí)現(xiàn)有序查找;
畫(huà)外音：求群覆蓋，哈希型實(shí)現(xiàn)的初始化更快，復(fù)雜度是O(M*N)。
第二步，如何判斷兩個(gè)(多個(gè))集合要不要合并?
集合對(duì)set(i)和set(j)，判斷里面有沒(méi)有重復(fù)元素，如果有，就需要合并，判重的偽代碼是：
- // 對(duì)set(i)和set(j)進(jìn)行元素判斷并合并
- (1) foreach (element in set(i))
- (2) if (element in set(j))
- merge(set(i), set(j));
第一行(1)遍歷第一個(gè)集合set(i)中的所有元素element;
畫(huà)外音：這一步的時(shí)間復(fù)雜度是O(N)。
第二行(2)判斷element是否在第二個(gè)集合set(j)中;
畫(huà)外音：如果使用哈希型set，第二行(2)的平均時(shí)間復(fù)雜度是O(1)。
這一步的時(shí)間復(fù)雜度至少是O(N)*O(1)=O(N)。
第三步，如何合并集合?
集合對(duì)set(i)和set(j)如果需要合并，只要把一個(gè)集合中的元素插入到另一個(gè)集合中即可：
- // 對(duì)set(i)和set(j)進(jìn)行集合合并
- merge(set(i), set(j)){
- (1) foreach (element in set(i))
- (2) set(j).insert(element);
- }
第一行(1)遍歷第一個(gè)集合set(i)中的所有元素element;
畫(huà)外音：這一步的時(shí)間復(fù)雜度是O(N)。
第二行(2)把element插入到集合set(j)中;
畫(huà)外音：如果使用哈希型set，第二行(2)的平均時(shí)間復(fù)雜度是O(1)。
這一步的時(shí)間復(fù)雜度至少是O(N)*O(1)=O(N)。
第四步：迭代第二步與第三步，直至結(jié)束
對(duì)于M個(gè)集合，暴力針對(duì)所有集合對(duì)，進(jìn)行重復(fù)元素判斷并合并，用兩個(gè)for循環(huán)可以暴力解決：
- (1)for(i = 1 to M)
- (2) for(j= i+1 to M)
- //對(duì)set(i)和set(j)進(jìn)行元素判斷并合并
- foreach (element in set(i))
- if (element in set(j))
- merge(set(i), set(j));
遞歸調(diào)用，兩個(gè)for循環(huán)，復(fù)雜度是O(M*M)。
綜上，如果這么解決群覆蓋的問(wèn)題，時(shí)間復(fù)雜度至少是：
- O(M*N) // 集合初始化的過(guò)程
- +
- O(M*M) // 兩重for循環(huán)遞歸
- *
- O(N) // 判重
- *
- O(N) // 合并
畫(huà)外音：實(shí)際復(fù)雜度要高于這個(gè)，隨著集合的合并，集合元素會(huì)越來(lái)越多，判重和合并的成本會(huì)越來(lái)越高。
第三部分：染色法
總的來(lái)說(shuō)，暴力法效率非常低，集合都是一個(gè)一個(gè)合并的，同一個(gè)元素在合并的過(guò)程中要遍歷很多次。很容易想到一個(gè)優(yōu)化點(diǎn)，能不能一次合并多個(gè)集合?
暴力法中，判斷兩個(gè)集合se<i>t和set<j>是否需要合并，思路是：遍歷set中的所有element，看在set中是否存在，如果存在，說(shuō)明存在交集，則需要合并。
哪些集合能夠一次性合并?
當(dāng)某些集合中包含同一個(gè)元素時(shí)，可以一次性合并。
怎么一次性發(fā)現(xiàn)，哪些集合包含同一個(gè)元素，并合并去重呢?
回顧一下工作中的類(lèi)似需求：
M個(gè)文件，每個(gè)文件包含N個(gè)用戶名，或者N個(gè)手機(jī)號(hào)，如何合并去重?
最常見(jiàn)的玩法是：
- cat file_1 file_2 … file_M | sort | uniq > result
這里的思路是什么?
(1) 把M*N個(gè)用戶名/手機(jī)號(hào)輸出;
(2) sort排序，排序之后相同的元素會(huì)相鄰;
(3) uniq去重，相鄰元素如果相同只保留一個(gè);
“排序之后相同的元素會(huì)相鄰”，就是一次性找出所有可合并集合的關(guān)鍵，這是染色法的核心。
舉一個(gè)栗子：
假設(shè)有6個(gè)微信群，每個(gè)微信群有若干個(gè)用戶：
- s1={1,0,5} s2={3,1} s3={2,9}
- s4={4,6} s5={4,7} s6={1,8}
假設(shè)使用樹(shù)形set來(lái)表示集合。
首先，給同一個(gè)集合中的所有元素染上相同的顏色，表示來(lái)自同一個(gè)集合。
然后，對(duì)所有的元素進(jìn)行排序，會(huì)發(fā)現(xiàn)：
(1) 相同的元素一定相鄰，并且一定來(lái)自不同的集合;
(2) 同一個(gè)顏色的元素被打散了;
這些相鄰且相同的元素，來(lái)自哪一個(gè)集合，這些集合就是需要合并的，如上圖：
(1) 粉色的1來(lái)自集合s1，紫色的1來(lái)自集合s2，黃色的1來(lái)自集合s6，所以s1s2s6需要合并;
(2) 藍(lán)色的4來(lái)自集合s4，青色的4來(lái)自集合s5，所以s4s5需要合并;
不用像暴力法遍歷所有的集合對(duì)，而是一個(gè)排序動(dòng)作，就能找到所有需要合并的集合。
畫(huà)外音：暴力法一次處理2個(gè)集合，染色法一次可以合并N個(gè)集合。
集合合并的過(guò)程，可以想象為，相同相鄰元素所在集合，染成第一個(gè)元素的顏色：
(1) 紫色和黃色，染成粉色;
(2) 青色，染成藍(lán)色;
最終，剩余三種顏色，也就是三個(gè)集合：
- s1={0,1,3,5,8}
- s3={2,9}
- s4={4,6,7}
神奇不神奇!!!
染色法有意思么?但仍有兩個(gè)遺留問(wèn)題：
(1) 粉色1，紫色1，黃色1，三個(gè)元素如何找到這三個(gè)元素所在的集合s1s2s6呢?
(2) s1s2s6三個(gè)集合如何快速合并?
畫(huà)外音：假設(shè)總元素個(gè)數(shù)n=M*N，如果使用樹(shù)形set，合并的復(fù)雜度為O(n*lg(n))，即O(M*N*lg(M*N))。
我們繼續(xù)往下看。
第四部分：鏈表法
染色法遺留了兩個(gè)問(wèn)題：
- 步驟(2)中，如何通過(guò)元素快速定位集合?
- 步驟(3)中，如何快速合并集合?
我們繼續(xù)聊聊這兩個(gè)問(wèn)題的優(yōu)化思路。
問(wèn)題一：如何由元素快速定位集合?
普通的集合，只能由集合根(root)定位元素，不能由元素逆向定位root，如何支持元素逆向定位root呢?
很容易想到，每個(gè)節(jié)點(diǎn)增加一個(gè)父指針即可。
更具體的：
- element{
- int data;
- element* left;
- element* right;
- }
升級(jí)為：
- element{
- element* parent; // 指向父節(jié)點(diǎn)
- int data;
- element* left;
- element* right;
- }
如上圖：所有節(jié)點(diǎn)的parent都指向它的上級(jí)，而只有root->parent=NULL。
對(duì)于任意一個(gè)元素，找root的過(guò)程為：
- element* X_find_set_root(element* x){
- element* temp=x;
- while(temp->parent != NULL){
- temptemp= temp->parent;
- }
- return temp;
- }
很容易發(fā)現(xiàn)，由元素找集合根的時(shí)間復(fù)雜度是樹(shù)的高度，即O(lg(n))。
有沒(méi)有更快的方法呢?
進(jìn)一步思考，為什么每個(gè)節(jié)點(diǎn)要指向父節(jié)點(diǎn)，直接指向根節(jié)點(diǎn)是不是也可以。
更具體的：
- element{
- int data;
- element* left;
- element* right;
- }
升級(jí)為：
- element{
- element* root; // 指向集合根
- int data;
- element* left;
- element* right;
- }
如上圖：所有節(jié)點(diǎn)的parent都指向集合的根。
對(duì)于任意一個(gè)元素，找root的過(guò)程為：
- element* X_find_set_root(element* x){
- return x->root;
- }
很容易發(fā)現(xiàn)，升級(jí)后，由元素找集合根的時(shí)間復(fù)雜度是O(1)。
畫(huà)外音：不能更快了吧。
另外，這種方式，能在O(1)的時(shí)間內(nèi)，判斷兩個(gè)元素是否在同一個(gè)集合內(nèi)：
- bool in_the_same_set(element* a, element* b){
- return (a->root == b->root);
- }
甚為方便。
畫(huà)外音：兩個(gè)元素的根相同，就在同一個(gè)集合內(nèi)。
問(wèn)題二：如何快速進(jìn)行集合合并?
暴力法中提到過(guò)，集合合并的偽代碼為：
- merge(set(i), set(j)){
- foreach(element in set(i))
- set(j).insert(element);
- }
把一個(gè)集合中的元素插入到另一個(gè)集合中即可。
假設(shè)set(i)的元素個(gè)數(shù)為n1，set(j)的元素個(gè)數(shù)為n2，其時(shí)間復(fù)雜度為O(n1*lg(n2))。
在“微信群覆蓋”這個(gè)業(yè)務(wù)場(chǎng)景下，隨著集合的不斷合并，集合高度越來(lái)越高，合并會(huì)越來(lái)越慢，有沒(méi)有更快的集合合并方式呢?
仔細(xì)回顧一下：
(1) 樹(shù)形set的優(yōu)點(diǎn)是，支持有序查找，省空間;
(2) 哈希型set的優(yōu)點(diǎn)是，快速插入與查找;
而“微信群覆蓋”場(chǎng)景對(duì)集合的頻繁操作是：
(1) 由元素找集合根;
(2) 集合合并;
那么，為什么要用樹(shù)形結(jié)構(gòu)或者哈希型結(jié)構(gòu)來(lái)表示集合呢?
畫(huà)外音：優(yōu)點(diǎn)完全沒(méi)有利用上嘛。
讓我們來(lái)看看，這個(gè)場(chǎng)景中，如果用鏈表來(lái)表示集合會(huì)怎么樣，合并會(huì)不會(huì)更快?
- s1={7,3,1,4}
- s2={1,6}
如上圖，分別用鏈表來(lái)表示這兩個(gè)集合?？梢钥吹?，為了滿足“快速由元素定位集合根”的需求，每個(gè)元素仍然會(huì)指向根。
s1和s2如果要合并，需要做兩件事：
- 集合1的尾巴，鏈向集合2的頭(藍(lán)線1);
- 集合2的所有元素，指向集合1的根(藍(lán)線2,3);
合并完的效果是：
變成了一個(gè)更大的集合。
假設(shè)set(1)的元素個(gè)數(shù)為n1，set(2)的元素個(gè)數(shù)為n2，整個(gè)合并的過(guò)程的時(shí)間復(fù)雜度是O(n2)。
畫(huà)外音：時(shí)間耗在set(2)中的元素變化。
咦，我們發(fā)現(xiàn)：
(1) 將短的鏈表，接到長(zhǎng)的鏈表上;
(2) 將長(zhǎng)的鏈表，接到短的鏈表上;
所使用的時(shí)間是不一樣的。
為了讓時(shí)間更快，一律使用更快的方式：“元素少的鏈表”主動(dòng)接入到“元素多的鏈表”的尾巴后面。這樣，改變的元素個(gè)數(shù)能更少一些，這個(gè)優(yōu)化被稱(chēng)作“加權(quán)合并”。
對(duì)于M個(gè)微信群，平均每個(gè)微信群N個(gè)用戶的場(chǎng)景，用鏈表的方式表示集合，按照“加權(quán)合并”的方式合并集合，最壞的情況下，時(shí)間復(fù)雜度是O(M*N)。
畫(huà)外音：假設(shè)所有的集合都要合并，共M次，每次都要改變N個(gè)元素的根指向，故為O(M*N)。
于是，對(duì)于“M個(gè)群，每個(gè)群N個(gè)用戶，微信群求覆蓋”問(wèn)題，使用“染色法”加上“鏈表法”，核心思路三步驟：
(1) 全部元素全局排序;
(2) 全局排序后，不同集合中的相同元素，一定是相鄰的，通過(guò)相同相鄰的元素，一次性找到所有需要合并的集合;
(3) 合并這些集合，算法完成;
其中：
- 步驟(1)，全局排序，時(shí)間復(fù)雜度O(M*N);
- 步驟(2)，染色思路，能夠迅猛定位哪些集合需要合并，每個(gè)元素增加一個(gè)屬性指向集合根，實(shí)現(xiàn)O(1)級(jí)別的元素定位集合;
- 步驟(3)，使用鏈表表示集合，使用加權(quán)合并的方式來(lái)合并集合，合并的時(shí)間復(fù)雜度也是O(M*N);
總時(shí)間復(fù)雜度是：
- O(M*N) //排序
- +
- O(1) //由元素找到需要合并的集合
- *
- O(M*N) //集合合并
神奇不神奇!!!
神奇不止一種，還有其他方法嗎?我們接著往下看。
第五部分：并查集法
分離集合(disjoint set)是一種經(jīng)典的數(shù)據(jù)結(jié)構(gòu)，它有三類(lèi)操作：
- Make-set(a)：生成一個(gè)只有一個(gè)元素a的集合;
- Union(X, Y)：合并兩個(gè)集合X和Y;
- Find-set(a)：查找元素a所在集合，即通過(guò)元素找集合;
這種數(shù)據(jù)結(jié)構(gòu)特別適合用來(lái)解決這類(lèi)集合合并與查找的問(wèn)題，又稱(chēng)為并查集。
能不能利用并查集來(lái)解決求“微信群覆蓋”問(wèn)題呢?
一、并查集的鏈表實(shí)現(xiàn)
鏈表法里基本聊過(guò)，為了保證知識(shí)的系統(tǒng)性，這里再稍微回顧一下。
如上圖，并查集可以用鏈表來(lái)實(shí)現(xiàn)。
鏈表實(shí)現(xiàn)的并查集，F(xiàn)ind-set(a)的時(shí)間復(fù)雜度是多少?
集合里的每個(gè)元素，都指向“集合的句柄”，這樣可以使得“查找元素a所在集合S”，即Find-set(a)操作在O(1)的時(shí)間內(nèi)完成。
鏈表實(shí)現(xiàn)的并查集，Union(X, Y)的時(shí)間復(fù)雜度是多少?
假設(shè)有集合：
- S1={7,3,1,4}
- S2={1,6}
合并S1和S2兩個(gè)集合，需要做兩件事情：
(1) 第一個(gè)集合的尾元素，鏈向第二個(gè)集合的頭元素(藍(lán)線1);
(2) 第二個(gè)集合的所有元素，指向第一個(gè)集合的句柄(藍(lán)線2,3);
合并完的效果是：
變成了一個(gè)更大的集合S1。
集合合并時(shí)，將短的鏈表，往長(zhǎng)的鏈表上接，這樣變動(dòng)的元素更少，這個(gè)優(yōu)化叫做“加權(quán)合并”。
畫(huà)外音：實(shí)現(xiàn)的過(guò)程中，集合句柄要存儲(chǔ)元素個(gè)數(shù)，頭元素，尾元素等屬性，以方便上述操作進(jìn)行。
假設(shè)每個(gè)集合的平均元素個(gè)數(shù)是n，Union(X, Y)操作的時(shí)間復(fù)雜度是O(n)。
能不能Find-set(a)與Union(X, Y)都在O(1)的時(shí)間內(nèi)完成呢?
可以，這就引發(fā)了并查集的第二種實(shí)現(xiàn)方法。
二、并查集的有根樹(shù)實(shí)現(xiàn)
什么是有根樹(shù)，和普通的樹(shù)有什么不同?
常用的set，就是用普通的二叉樹(shù)實(shí)現(xiàn)的，其元素的數(shù)據(jù)結(jié)構(gòu)是：
- element{
- int data;
- element* left;
- element* right;
- }
通過(guò)左指針與右指針，父親節(jié)點(diǎn)指向兒子節(jié)點(diǎn)。
而有根樹(shù)，其元素的數(shù)據(jù)結(jié)構(gòu)是：
- element{
- int data;
- element* parent;
- }
通過(guò)兒子節(jié)點(diǎn)，指向父親節(jié)點(diǎn)。
假設(shè)有集合：
- S1={7,3,1,4}
- S2={1,6}
通過(guò)如果通過(guò)有根樹(shù)表示，可能是這樣的：
所有的元素，都通過(guò)parent指針指向集合句柄，所有元素的Find-set(a)的時(shí)間復(fù)雜度也是O(1)。
畫(huà)外音：假設(shè)集合的首個(gè)元素，代表集合句柄。
有根樹(shù)實(shí)現(xiàn)的并查集，Union(X, Y)的過(guò)程如何?時(shí)間復(fù)雜度是多少?
通過(guò)有根樹(shù)實(shí)現(xiàn)并查集，集合合并時(shí)，直接將一個(gè)集合句柄，指向另一個(gè)集合即可。
如上圖所示，S2的句柄，指向S1的句柄，集合合并完成：S2消亡，S1變?yōu)榱烁蟮募稀?/p>
容易知道，集合合并的時(shí)間復(fù)雜度為O(1)。
會(huì)發(fā)現(xiàn)，集合合并之后，有根樹(shù)的高度變高了，與“加權(quán)合并”的優(yōu)化思路類(lèi)似，總是把節(jié)點(diǎn)數(shù)少的有根樹(shù)，指向節(jié)點(diǎn)數(shù)多的有根樹(shù)(更確切的說(shuō)，是高度矮的樹(shù)，指向高度高的樹(shù))，這個(gè)優(yōu)化叫做“按秩合并”。
新的問(wèn)題來(lái)了，集合合并之后，不是所有元素的Find-set(a)操作都是O(1)了，怎么辦?
如圖S1與S2合并后的新S1，首次“通過(guò)元素6來(lái)找新S1的句柄”，不能在O(1)的時(shí)間內(nèi)完成了，需要兩次操作。
但為了讓未來(lái)“通過(guò)元素6來(lái)找新S1的句柄”的操作能夠在O(1)的時(shí)間內(nèi)完成，在首次進(jìn)行Find-set(“6”)時(shí)，就要將元素6“尋根”路徑上的所有元素，都指向集合句柄，如下圖。
某個(gè)元素如果不直接指向集合句柄，首次Find-set(a)操作的過(guò)程中，會(huì)將該路徑上的所有元素都直接指向句柄，這個(gè)優(yōu)化叫做“路徑壓縮”。
畫(huà)外音：路徑上的元素第二次執(zhí)行Find-set(a)時(shí)，時(shí)間復(fù)雜度就是O(1)了。
實(shí)施“路徑壓縮”優(yōu)化之后，F(xiàn)ind-set的平均時(shí)間復(fù)雜度仍是O(1)。
稍微總結(jié)一下。
通過(guò)鏈表實(shí)現(xiàn)并查集：
(1) Find-set的時(shí)間復(fù)雜度，是O(1)常數(shù)時(shí)間;
(2) Union的時(shí)間復(fù)雜度，是集合平均元素個(gè)數(shù)，即線性時(shí)間;
畫(huà)外音：別忘了“加權(quán)合并”優(yōu)化。
通過(guò)有根樹(shù)實(shí)現(xiàn)并查集：
(1) Union的時(shí)間復(fù)雜度，是O(1)常數(shù)時(shí)間;
(2) Find-set的時(shí)間復(fù)雜度，通過(guò)“按秩合并”與“路徑壓縮”優(yōu)化后，平均時(shí)間復(fù)雜度也是O(1);
即，使用并查集，非常適合解決“微信群覆蓋”問(wèn)題。
知其然，知其所以然，思路往往比結(jié)果更重要。
算法，其實(shí)還是挺有意思的。
【本文為51CTO專(zhuān)欄作者“58沈劍”原創(chuàng)稿件，轉(zhuǎn)載請(qǐng)聯(lián)系原作者】
