暴力法求解“微信群覆蓋”？
題目：求微信群覆蓋
微信有很多群，現(xiàn)進(jìn)行如下抽象：
- 每個(gè)微信群由一個(gè)***的gid標(biāo)識(shí);
- 微信群內(nèi)每個(gè)用戶由一個(gè)***的uid標(biāo)識(shí);
- 一個(gè)用戶可以加入多個(gè)群;
- 群可以抽象成一個(gè)由不重復(fù)uid組成的集合，例如：
- g1{u1, u2, u3}
- g2{u1, u4, u5}
可以看到，用戶u1加入了g1與g2兩個(gè)群。
畫外音，注意：
- gid和uid都是uint64;
- 集合內(nè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}；
畫外音：集合g1中包含u1，集合g2中包含u1，合并后的微信群g3也只包含一個(gè)u1。
(2) 不斷的進(jìn)行上述操作，直到剩下所有的微信群都不含相同的用戶為止;
將上述操作稱：求群的覆蓋。
設(shè)計(jì)算法，求群的覆蓋，并說明算法時(shí)間與空間復(fù)雜度。
畫外音：58同城2013年校招筆試題。
對(duì)于一個(gè)復(fù)雜的問題，思路肯定是“先解決，再優(yōu)化”，大部分人不是神，很難一步到位。先用一種比較“笨”的方法解決，再看“笨方法”有什么痛點(diǎn)，優(yōu)化各個(gè)痛點(diǎn)，不斷升級(jí)方案。
拿到這個(gè)問題，很容易想到的思路是：
- 先初始化M個(gè)集合，用集合來表示微信群gid與用戶uid的關(guān)系;
- 找到哪兩個(gè)(哪些)集合需要合并;
- 接著，進(jìn)行集合的合并;
- 迭代步驟二和步驟三，直至所有集合都沒有相同元素，算法結(jié)束;
***步，如何初始化集合?
set這種數(shù)據(jù)結(jié)構(gòu)，大家用得很多，來表示集合：
- 新建M個(gè)set來表示M個(gè)微信群gid
- 每個(gè)set插入N個(gè)元素來表示微信群中的用戶uid
set有兩種最常見的實(shí)現(xiàn)方式，一種是樹型set，一種是哈希型set。
假設(shè)有集合：
- s={7, 2, 0, 14, 4, 12}
樹型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)有序查找
畫外音：求群覆蓋，哈希型實(shí)現(xiàn)的初始化更快，復(fù)雜度是O(M*N)。
第二步，如何判斷兩個(gè)(多個(gè))集合要不要合并?
集合對(duì)set(i)和set(j)，判斷里面有沒有重復(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;
畫外音：這一步的時(shí)間復(fù)雜度是O(N)。
第二行(2)判斷element是否在第二個(gè)集合set(j)中;
畫外音：如果使用哈希型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;
畫外音：這一步的時(shí)間復(fù)雜度是O(N)。
第二行(2)把element插入到集合set(j)中;
畫外音：如果使用哈希型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)。
綜上，如果這么解決群覆蓋的問題，時(shí)間復(fù)雜度至少是：
- O(M*N) // 集合初始化的過程
- +
- O(M*M) // 兩重for循環(huán)遞歸
- *
- O(N) // 判重
- *
- O(N) // 合并
畫外音：實(shí)際復(fù)雜度要高于這個(gè)，隨著集合的合并，集合元素會(huì)越來越多，判重和合并的成本會(huì)越來越高。
基于“先解決，再優(yōu)化”的思想，很多優(yōu)化方向的問題，自然而然的從腦中蹦出：
(1) 能不能快速通過元素定位集合?
畫外音：
- 通過集合查元素，哈希型set時(shí)間復(fù)雜度是O(1);
- 通過元素查集合(句柄)，如何來實(shí)現(xiàn)呢?
(2) 能不能快速進(jìn)行集合合并?
(3) 能不能一次合并多個(gè)集合?
經(jīng)典數(shù)據(jù)結(jié)構(gòu)，分離集合(disjoint set)，它有三類操作：
- Make-set(a)：生成一個(gè)只有一個(gè)元素a的集合;
- Union(X, Y)：合并兩個(gè)集合X和Y;
- Find-set(a)：查找元素a所在集合，即通過元素找集合;
特別適合用來解決這類集合合并與查找的問題，又稱為并查集。
如何利用并查集來解決求“微信群覆蓋”問題，是后文將要介紹的內(nèi)容。
畫外音：先介紹“并查集”這一種方案，后續(xù)再介紹其他方案。
知道并查集的思路和原理，比知道什么是并查集更重要。
算法，其實(shí)還是挺有意思的。
【本文為51CTO專欄作者“58沈劍”原創(chuàng)稿件，轉(zhuǎn)載請(qǐng)聯(lián)系原作者】
