首页 新闻 论坛 群组 Blog 文档 下载 读书 Tag 网摘 搜索 .NET Java 游戏 视频 人才 外包 培训 数据库 书店 程序员
中国软件网
欢迎您:游客 | 登录 注册 帮助
    • 一道面试题 [无满意答案结贴]
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • nandizhu
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    • 揭贴率：
    发表于：2008-08-21 21:11:35 楼主
    一亿个整数里找出现次数最多的前N个数

    有没有比较好点的方法？？？
    20  修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • e_sharp
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-08-21 21:30:451楼 得分:0
    mark
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • buzhiyao
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-08-21 21:35:472楼 得分:0
    mark
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • panda_lin
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-08-21 22:15:133楼 得分:0
    最简单的方法，用stl的map做。
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • richbirdandy
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-08-21 23:29:404楼 得分:0
    想到几个思路 没有特别针对这道题的 等高手解答吧
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • traso
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-08-22 03:09:545楼 得分:0
    mark  关注.
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • jdifjoifj
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-08-22 08:44:566楼 得分:0
    该回复于2008-08-25 13:06:18被版主删除
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • xianyuxiaoqiang
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-08-22 13:50:417楼 得分:0
    1亿==100M
    开辟200M内存够了...
    array[100000000]
    初始化为0

    从文件里读入数据到source[100000000]数组中。
    遍历source[]：
    array[source[i]-1]++;
    i=0...99999999

    定义数组
    result[N]

    问题简化为：从array中选出N个下标值，它们对应了array中存储的最大的N个数。

    比如array[0]=50000000，array[1]=50000000，那么result[0]=0+1=1
    result[1]=1+1=2


    献丑了。
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • peach5460
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-08-25 10:30:008楼 得分:0
    mark
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • coverallwangp
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-08-25 10:39:469楼 得分:0
    遍历每一个元素（如果内存不能全部装入，可以一部分一部分的装）

    typedef tagM
    {
      int Num;
      int  count;
    }

    如果这个元素没有出现过，则建立一个新的结构tagM,Num是这个元素的值，count是这个元素已经出现的次数
    如果这个元素已经出现过，则将相应结构的计数count加1

    最后取计数大的前N个
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • Lx_china
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-08-25 11:21:4010楼 得分:0
    占个坑，好好想想，顺便等高手回答
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • freedomzcd
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-08-25 11:53:5211楼 得分:0
    呃.....
    关注..
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • zhirom
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-08-25 13:17:5912楼 得分:0
    用hash函数,用一个响应的变量记录重复的次数
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • jeansmy111
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-08-25 17:15:2913楼 得分:0
    指出“七樓”錯誤:數組不能申請200M內存空間，這是不合法的。
    數組所能申請的內存空間小於2M。用數組對於這道題是行不通的。

    建議：
    　　本題的關鍵是這一億個數怎麼存儲和操作的問題。
    　　有二種方法可以解決：1，用外數據存儲方法
    　　　　　　　　　　　　2，用二叉樹
    　　建議閱讀數據結構最後二章。
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • panda_lin
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-08-26 10:05:3414楼 得分:0
    想用二叉树的话STL的map已经解决的很好了。开大内存不现实。如果内存有限，那就二叉树也没法解决了，用外部存储吧。
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • ateen
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-08-26 10:09:2715楼 得分:0
    占楼，关注中~
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • hqin6
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-08-26 10:17:3716楼 得分:0
    数目太多了~
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • rendao0563
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-08-26 18:02:3817楼 得分:0
    引用 7 楼 xianyuxiaoqiang 的回复:
    1亿==100M
    开辟200M内存够了...
    array[100000000]
    初始化为0

    从文件里读入数据到source[100000000]数组中。
    遍历source[]：
    array[source[i]-1]++;
    i=0...99999999

    定义数组
    result[N]

    问题简化为：从array中选出N个下标值，它们对应了array中存储的最大的N个数。

    比如array[0]=50000000，array[1]=50000000，那么result[0]=0+1=1
    result[1]=1+1=2


    献丑了。


    不错,只需要遍历一次.200M连续空间很轻松就可以申请到的. 如果数据更大.可以hash到多台机器上.
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • rockyrl
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-08-26 18:51:5018楼 得分:0
    引用 7 楼 xianyuxiaoqiang 的回复:
    1亿==100M
    开辟200M内存够了...
    array[100000000]
    初始化为0

    从文件里读入数据到source[100000000]数组中。
    遍历source[]：
    array[source[i]-1]++;
    i=0...99999999

    定义数组
    result[N]

    问题简化为：从array中选出N个下标值，它们对应了array中存储的最大的N个数。

    比如array[0]=50000000，array[1]=50000000，那么result[0]=0+1=1
    result[1]=1+1=2


    献丑了。

    不懂你这是什么意思，array[source[i]-1]++是表示为文件中每一个数分配一个计数的单元么？那整数的大小超过1亿了怎么办？一共1亿个整数不代表最大就1亿。
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • rockyrl
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-08-26 19:00:1619楼 得分:0
    引用 7 楼 xianyuxiaoqiang 的回复:
    1亿==100M
    开辟200M内存够了...
    array[100000000]
    初始化为0

    从文件里读入数据到source[100000000]数组中。
    遍历source[]：
    array[source[i]-1]++;
    i=0...99999999

    定义数组
    result[N]

    问题简化为：从array中选出N个下标值，它们对应了array中存储的最大的N个数。

    比如array[0]=50000000，array[1]=50000000，那么result[0]=0+1=1
    result[1]=1+1=2


    献丑了。

    array的大小应该包含到所有可能的整数，如果整数是32位，array应该分配G级的空间了
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • satinelam
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-08-27 10:06:3720楼 得分:0
    mark
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • freedomzcd
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-08-27 11:35:2921楼 得分:0
    嗯...某楼果然是献丑了...o(∩_∩)o...
    继续关注...
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • duanyongzhi
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-08-27 14:26:4522楼 得分:0
    引用 21 楼 freedomzcd 的回复:
    嗯...某楼果然是献丑了...o(∩_∩)o...
    继续关注...

    自已想不出来，却想去笑别人。浮云啊浮云。
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • starstarstone
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-08-27 21:33:4923楼 得分:0
    引用 7 楼 xianyuxiaoqiang 的回复:
    1亿==100M
    开辟200M内存够了... /////////////////////////////////应该根据整数的范围开辟空间，而不是整数的个数
    array[100000000]
    初始化为0

    从文件里读入数据到source[100000000]数组中。
    遍历source[]：
    array[source[i]-1]++;
    i=0...99999999

    定义数组
    result[N]

    问题简化为：从array中选出N个下标值，它们对应了array中存储的最大的N个数。

    比如array[0]=50000000，array[1]=50000000，那么result[0]=0+1=1
    result[1]=1+1=2


    献丑了。

    -----------------------------------------------------
    以无符号整型数为例
    定义array[65536]并初始化为0
    假设这一亿个数在source[100000000]中
    遍历source[]：
    array[source[i]-1]++;
    i=0...99999999
    这时，array[x]就是x出现的次数
    从array中选出N个下标值，它们对应了array中最大的N个数，这N个下标就是楼主要找的N个数
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • j8daxue
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-08-31 02:26:4424楼 得分:0
    看下编程之美上面类似的题
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • wxmowen
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-08-31 10:17:1425楼 得分:0
    太夸张了吧，动不动就要申请大内存啊。。一定会还有更好的办法的
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • hecho
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-09-02 20:25:2826楼 得分:0
    占个位置等好的方法!!
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • kings_zqz
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-09-03 23:01:3827楼 得分:0
    mark
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • langellan
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-09-03 23:29:4728楼 得分:0
    这里面好像考的是算法，我不会，看看高手能不能给个好的设计方式
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • Kasmile
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-09-03 23:51:3929楼 得分:0
    引用 26 楼 hecho 的回复:
    占个位置等好的方法!!
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • hotonion
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-09-04 09:39:3230楼 得分:0
    mark
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • fallening
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-09-04 09:45:4531楼 得分:0
    std::nth_element
    修改 删除 举报 引用 回复