DataStructure

使用map降低算法的时间复杂度

在前两周在开发新接口时,遇到了今天要介绍的两种场景,我都通过map降低了整个算法的时间复杂度。我认为有必要记录一下思考过程,也顺便分享给各位读者。虽然简单,但确实很好用。 1. 群组中的好友 背景 各位读者应该都知道在微信聊天框中输入@之后,会出现各群员的列表。新接口功能上差不多,只是在这基础上还要加上一个限制条件:“列表中的群成员必须是好友”。我可以从其他微服务已经有的“好友接口”获取某一个用户的好友列表(list),那么我只需要找出和群成员列表的交集即可。 实现 当时想到有两种方法可以实现上面说的效果(设群有N个群成员,M个好友): 采用两层遍历查询方式,遍历群成员list + 二分查找好友list(查询的时间复杂度:O(N * logM)) 采用map,将群成员id作为map的key,role作为value(查询的时间复杂度:O(1)) 哪种方式更好?通过时间复杂度来看,答案就不言而喻了。部分代码如下: // 获取群内成员(我的源码有用到role做别的业务逻辑处理) func GetMemberInGroup(groupID int64) (map[int64]int8, error) dataSet := make(map[int64]int8) strSql :=...

Continue reading...