暴力法求解“微信群覆盖”?
题目:求微信群覆盖 微信有很多群,现进行如下抽象: (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年校招笔试题。 对于一个复杂的问题,思路肯定是“先解决,再优化...