链表法求解“微信群覆盖”

相关阅读:
  1. 暴力法求解“微信群覆盖
  2. 染色法求解“微信群覆盖
  3. 链表法求解“微信群覆盖
  4. 并查集求解“微信群覆盖

题目:求微信群覆盖


微信有很多群,现进行如下抽象:

(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)    //集合合并


希望大家有收获。


这几篇文章是在讲解决问题的思路,是希望大家从思路中得到启示,如果阅读完文字,能引发一些思考,能有一些收获,就是好的。是不是“并查集”真的这么重要么?


思路比结论重要,有收获就是好的。


转载自公众号:架构师之路,若有侵权,请联系作者进行删除.

  IT.互联网   技术

作者  :  金樽

一件事,想通了是天堂,想不通就是地狱




小程序

面试一点通

创作中心

分享职场知识、帮助到更多的人

最新发布