暴力法求解“微信群覆盖”?
题目:求微信群覆盖
微信有很多群,现进行如下抽象:
(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) 先初始化M个集合,用集合来表示微信群gid与用户uid的关系;
(2) 找到哪两个(哪些)集合需要合并;
(3) 接着,进行集合的合并;
(4) 迭代步骤二和步骤三,直至所有集合都没有相同元素,算法结束;
第一步,如何初始化集合?
set这种数据结构,大家用得很多,来表示集合:
● 新建 M个set 来表示M个微信群gid● 每个set插入 N个元素 来表示微信群中的用户uid
set有两种最常见的实现方式,一种是树型set,一种是哈希型set。
假设有集合:
s={7, 2, 0, 14, 4, 12}
树型set的实现如下:
其特点是:
● 插入和查找的平均时间复杂度是 O(lg(n))● 能实现有序查找
● 省空间
哈希型set实现如下:
其特点是:
● 插入和查找的平均时间复杂度是 O(1)不能实现有序查找
画外音:求群覆盖,哈希型实现的初始化更快,复杂度是O(M*N)。
第二步,如何判断两个(多个)集合要不要合并?
集合对set(i)和set(j),判断里面有没有重复元素,如果有,就需要合并,判重的伪代码是:
// 对set(i)和set(j)进行元素判断并合并
(1) foreach (element in set(i))
(2) if (element in set(j))
merge(set(i), set(j));
第一行(1)遍历第一个集合set(i)中的所有元素element;
画外音:这一步的时间复杂度是O(N)。
第二行(2)判断element是否在第二个集合set(j)中;
画外音:如果使用哈希型set,第二行(2)的平均时间复杂度是O(1)。
这一步的时间复杂度至少是O(N)*O(1)=O(N)。
第三步,如何合并集合?
集合对set(i)和set(j)如果需要合并,只要把一个集合中的元素插入到另一个集合中即可:
// 对set(i)和set(j)进行集合合并
merge(set(i), set(j)){
(1) foreach (element in set(i))
(2) set(j).insert(element);
}
第一行(1)遍历第一个集合set(i)中的所有元素element;
画外音:这一步的时间复杂度是O(N)。
第二行(2)把element插入到集合set(j)中;
画外音:如果使用哈希型set,第二行(2)的平均时间复杂度是O(1)。
这一步的时间复杂度至少是O(N)*O(1)=O(N)。
第四步:迭代第二步与第三步,直至结束
对于M个集合,暴力针对所有集合对,进行重复元素判断并合并,用两个for循环可以暴力解决:
(1)for(i = 1 to M)
(2) for(j= i+1 to M)
//对set(i)和set(j)进行元素判断并合并
foreach (element in set(i))
if (element in set(j))
merge(set(i), set(j));
递归调用,两个for循环,复杂度是O(M*M)。
综上,如果这么解决群覆盖的问题,时间复杂度至少是:
O(M*N) // 集合初始化的过程
+
O(M*M) // 两重for循环递归
*
O(N) // 判重
*
O(N) // 合并
画外音:实际复杂度要高于这个,随着集合的合并,集合元素会越来越多,判重和合并的成本会越来越高。
基于“先解决,再优化”的思想,很多优化方向的问题,自然而然的从脑中蹦出:
(1) 能不能快速通过元素定位集合?
画外音:
通过集合查元素,哈希型set时间复杂度是O(1);
通过元素查集合(句柄),如何来实现呢?
(2) 能不能快速进行集合合并?
(3) 能不能一次合并多个集合?
经典数据结构,分离集合(disjoint set),它有三类操作:
Make-set(a):生成一个只有一个元素a的集合;
Union(X, Y):合并两个集合X和Y;
Find-set(a):查找元素a所在集合,即通过元素找集合;
特别适合用来解决这类集合合并与查找的问题,又称为并查集。
如何利用并查集来解决求“微信群覆盖”问题,是后文将要介绍的内容。
画外音:先介绍“并查集”这一种方案,后续再介绍其他方案。
知道并查集的思路和原理,比知道什么是并查集更重要。
算法,其实还是挺有意思的。
原文发布时间为:2018-11-13
本文作者:58沈剑
低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。
持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。
转载内容版权归作者及来源网站所有,本站原创内容转载请注明来源。
- 上一篇
HybridDB for MySQL计算规格全面加速OLAP场景
前言 在2018年双十一中,阿里云数据库HybridDB为几十万商家提供数据驱动的店铺智能服务,也为几千小二提供了高效的数据化服务产品,大大提高生产效率。 盒马实时交易大盘使用HybridDB实现盒马全链路的数据实时闭环,支撑1000多张表的复杂查询,平均查询延迟1秒以内,大大提高了新零售的数据化能力。菜鸟仓储实时在线数仓,基于HybridDB for MySQL构建了容纳核心的订单、包裹、库存及时效等全链路数据,目前已经成长为菜鸟仓储业务的数据化产品基石。 HybridDB 承接ECS、RDS、CDN、SLB等阿里云核心业务提供实时监控数据的存储、计算服务,以及支撑了四大件产品双十一实时监控大屏。为阿里云双十一保驾护航。 经过双十一的洗礼后,HybridDB for MySQL最新推出OLAP增强的高性能计算规格,通过自研的列式存储引擎CStore全面加速分析场景。主打毫秒级实时数据更新+百亿大表任意维度毫秒级分析,在完备的SQL能力上,同时支持在SQL中的多值子列查询、全文检索、空间检索等功能特性。既支持通过数据同步工具实时写入数据也支持直接和离线数仓ODPS的快速数据TB每小时的...
- 下一篇
云数据库POLARDB优势解读系列文章之③——分钟级弹性
双11大考 POLARDB分钟级弹性让企业轻松扩展 无处不在的脉冲计算 阿里有双11,中国有春运,高考后有分数出来的那天,歌迷心中有周杰伦演唱会门票在线开售之时。。。。有人的地方就有江湖,有人的地方也有脉冲计算,这些热点事件背后都需要大量的计算资源给予支撑,而这些突然急需的计算资源就像脉冲一样,急迫而猛烈,我们称之为脉冲计算。不仅ECS服务器,数据库也需要应对这些突如其来的脉冲波动,才能保证整个系统的平滑稳定。 存储与计算分离 我们知道POLARDB一个最大的特点是存储与计算分离,所谓分离就是计算节点(DB Engine)和存储节点(DB Store)在不同的物理服务器上,任何落地到存储设备的I/O操作均为网络I/O。可能会有人问,走网络,延迟怎么样,性能好不好?在『性价比』这篇文章中简单介绍过借助PolarFS经过网络访问PolarSt
相关文章
文章评论
共有0条评论来说两句吧...
文章二维码
点击排行
-
Docker使用Oracle官方镜像安装(12C,18C,19C)
- Springboot2将连接池hikari替换为druid,体验最强大的数据库连接池
- CentOS8编译安装MySQL8.0.19
- Docker快速安装Oracle11G,搭建oracle11g学习环境
- SpringBoot2配置默认Tomcat设置,开启更多高级功能
- MySQL8.0.19开启GTID主从同步CentOS8
- CentOS7,8上快速安装Gitea,搭建Git服务器
- Jdk安装(Linux,MacOS,Windows),包含三大操作系统的最全安装
- SpringBoot2编写第一个Controller,响应你的http请求并返回结果
推荐阅读
最新文章
- MySQL8.0.19开启GTID主从同步CentOS8
- Springboot2将连接池hikari替换为druid,体验最强大的数据库连接池
- Docker快速安装Oracle11G,搭建oracle11g学习环境
- SpringBoot2整合Redis,开启缓存,提高访问速度
- Windows10,CentOS7,CentOS8安装Nodejs环境
- CentOS7编译安装Cmake3.16.3,解决mysql等软件编译问题
- Docker安装Oracle12C,快速搭建Oracle学习环境
- SpringBoot2编写第一个Controller,响应你的http请求并返回结果
- SpringBoot2更换Tomcat为Jetty,小型站点的福音
- CentOS7设置SWAP分区,小内存服务器的救世主