» 微民网码农多。。。求个算法。10w个联系人进行分组。。
    数学模型很简单 有10w个联系人。
    
    要把他们分组。
    
    也就是相等的放在一起。
    
    相等的条件是 名字 或者 电话号码 相同。
    
    比如说 有3个联系人 zhou：123 mushi：123 zhou：456
    
    那这3个联系人 就要放在一组。。
    
    在不考虑空间和 线程数量对cpu的影响下 。要求最快的速度把这10w个联系人完成分组 有什么好的算法么/？
    

网友评论2013-08-15 15:04

    不难吧
    建立一个 集合(user 10W用户信息)
    int k=0
    for(i=1,i<10w,i++){
    新建一个分组实体
    for(j=i+1,j<10w,j++){
     if(条件符合){
     分组实体.add(user)
     集合.delete(user)
     }
    }
    K++
    }
    结果 是K 是多少 就是有多少个分组
    

网友评论2013-08-15 15:19

    被一楼终结了？
    

网友评论2013-08-15 15:21

    不考虑空间，先建立个已经分类完的表
    
    然后一次赋值，齐活，O(1)...
    

网友评论2013-08-15 15:23

    Reply Post by yuanyixy123 (2013-08-15 15:04):
    
    不难吧
    建立一个 集合(user 10W用户信息)
    int k=0
    for(i=1,i<10w,i++){
    新建一个分组实体
    for(j=i+1,j<10w,j++){
     if(条件符合){
     分组实体.add(user)
     集合.delete(user)
     }
    }
    K++
    }
    结果 是K 是多少 就是有多少个分组
    
    现在就是用的这个方法 在最差的情况下。跑的太慢了。
    

网友评论2013-08-15 15:24

    如果是这种情况
    A 123
    B 123
    A 456
    D 456
    D 789
    那么这5个算一组吗？
    

网友评论2013-08-15 15:25

    就一楼的想法，lz是做cc的吧
    

网友评论2013-08-15 15:26

    看成排序了
    

网友评论2013-08-15 15:26

    Reply to Reply Post by mjutghn1226 (2013-08-15 15:23)
    
    那就百度下 排序方法好了 找到 匹配次数最少的算法 能提升一点性能 这个本身就有10W的量你们是要多快 才算快
    

网友评论2013-08-15 15:30

    我想可不可以这样：
    
    用一个HashMap，用姓名的hash值做key，后面每个记录的姓名hash一下然后到hashmap中查找，有这个key就放入一组，否则插入新key。
    
    不过hashmap底层是不是用linklist做的，好久没搞过了都忘记了。
    

网友评论2013-08-15 15:35

    理解错了 编辑掉
    

网友评论2013-08-15 15:41

    Reply Post by 东方未名 (2013-08-15 15:30):
    
    我想可不可以这样：
    
    用一个HashMap，用姓名的hash值做key，后面每个记录的姓名hash一下然后到hashmap中查找，有这个key就放入一组，否则插入新key。
    
    不过hashmap底层是不是用linklist做的，好久没搞过了都忘记了。
    
    我觉得是一张二维的哈希表，纵轴是姓名的hash，横轴是号码的hash，先用10w数据填充着张表，然后再通过条件一组一组取出来？
    

网友评论2013-08-15 16:00

    Reply Post by yuanyixy123 (2013-08-15 15:26):
    
    那就百度下 排序方法好了 找到 匹配次数最少的算法 能提升一点性能 这个本身就有10W的量你们是要多快 才算快
    
    实际的业务比这个复杂的多。我是换了一种数学模型来阐述这个业务需求。
    

网友评论2013-08-15 16:07

    Reply Post by 卡斯布儿 (2013-08-15 15:41):
    
    我觉得是一张二维的哈希表，纵轴是姓名的hash，横轴是号码的hash，先用10w数据填充着张表，然后再通过条件一组一组取出来？
    
    我现在改的算法 跟你差不多。有一定提升。但是hash 算法 要改一下。还在找。。。大学学的都忘光了。。hashcode值 范围太大 空间占用太高了。。
    
    数学一般的人真是难。。。不过还是谢谢你。。这条路应该优化一下 能继续走下去
    

网友评论2013-08-15 16:08

微民网码农多。。。求个算法。10w个联系人进行分组。。
    不考虑空间，那方法就是做多组二叉树，一次性设定好每种排序，比如名字，号码，男女…………然后提取的时候从不同的树中提取吧……根据名字的，就从名字来找，从效率来说，第一次慢点，以后每次寻找，判断次数不会超过32次吧
    

网友评论2013-08-15 19:48

    把名字和电话号码做成hash 然后用并查集合并
    复杂度O(n)
    

    
    
    

LOL罗辑思维全国人大代表真三搞笑视频柳岩