33,010
社区成员
发帖
与我相关
我的任务
分享请发表友善的回复…
发表回复
pptor 2007-11-20
- 打赏
- 举报
名字分姓和名 吗，把所有中国人的名字 按姓进行分类 重复最多的名字肯定是在那几个人口较多的姓里面
这样我们就可以从所有中国人里面先把那几个姓的名字给留下来
这样我们就可以从所有中国人里面先把那几个姓的名字给留下来
qzy6 2007-11-16
- 打赏
- 举报
ls说的我没怎么看懂，应当说清楚点。
目前我觉得较好的还是hash法，当然还有些细节可以讨论。
目前我觉得较好的还是hash法，当然还有些细节可以讨论。
syy6 2007-11-16
- 打赏
- 举报
其实腾讯这次笔试的题目
就是10亿个整数，找出中位数。
这个我还有思路，就是整型题目中说了是四个字节，因而有最大最小值。
可以分成若干组，遍历10亿个整数，得到频数。
找出中位数所在组，然后计算前后组的频数和，就可以得到中位数范围。
再次遍历，范围已知，此范围排序，再考虑范围前后的频数和，就可以得到中位数。
就是10亿个整数，找出中位数。
这个我还有思路，就是整型题目中说了是四个字节，因而有最大最小值。
可以分成若干组，遍历10亿个整数，得到频数。
找出中位数所在组，然后计算前后组的频数和，就可以得到中位数范围。
再次遍历，范围已知，此范围排序，再考虑范围前后的频数和，就可以得到中位数。
qzy6 2007-11-15
- 打赏
- 举报
ls说的没错，空间开销太大，考虑不成熟。
这个题目可以这样理解： 10亿个整数,扫描一遍找出重复次数最多的。
另外百度有道相似的：
寻找热门查询：
搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来，每个查询串的长度为1-255字节。假设目前有一千万个记录，这些查询串的重复度比较高，虽然总数是1千万，但如果除去重复后，不超过3百万个。一个查询串的重复度越高，说明查询它的用户越多，也就是越热门。请你统计最热门的10个查询串，要求使用的内存不能超过1G。
（1）请描述你解决这个问题的思路；
（2）请给出主要的处理流程，算法，以及算法的复杂度。
这个题目可以这样理解： 10亿个整数,扫描一遍找出重复次数最多的。
另外百度有道相似的：
寻找热门查询：
搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来，每个查询串的长度为1-255字节。假设目前有一千万个记录，这些查询串的重复度比较高，虽然总数是1千万，但如果除去重复后，不超过3百万个。一个查询串的重复度越高，说明查询它的用户越多，也就是越热门。请你统计最热门的10个查询串，要求使用的内存不能超过1G。
（1）请描述你解决这个问题的思路；
（2）请给出主要的处理流程，算法，以及算法的复杂度。
tailzhou 2007-11-15
- 打赏
- 举报
qzy6的方法其实就是键树；
树的深度不是问题，但每个节点的孩子节点太多，空间可能有问题；
树的深度不是问题，但每个节点的孩子节点太多，空间可能有问题；
qzy6 2007-11-15
- 打赏
- 举报
10~12楼作废
qzy6 2007-11-15
- 打赏
- 举报
进一步提高效率：
将二进制串转化为八进制串或十六进制串，可以减小深度。当然这时候就是B树了。
八进制串时平均访问深度为 6
十六进制串时平均访问深度为 3
将二进制串转化为八进制串或十六进制串，可以减小深度。当然这时候就是B树了。
八进制串时平均访问深度为 6
十六进制串时平均访问深度为 3
qzy6 2007-11-15
- 打赏
- 举报
另外，几乎所有的寻找集合中重复元素的问题都可以考虑这种算法。因为计算机中现在都是二进制编码的。
当然，也要考虑树的深度。
当然，也要考虑树的深度。
qzy6 2007-11-15
- 打赏
- 举报
试试这个算法： 线性的
假设汉字编码为GB2312十六进制编码，那么一个名字在计算机内存储表示为一系列的二进制位。譬如 “张三“，应当是一个32位的二进制位串，“张三丰”应当是一个48位的二进制位串。由于编码严格，所以名字不同，编码绝对不同。
算法思想：
建立一棵二叉树，类似哈夫曼编码树，遇0转向左子树，遇1转向右子树。每个节点设置一个计数器 count, 保存从根节点到该节点路径所代表的位串（其实代表一个名字）的重复次数。
对于每个名字，转化为位串，沿二叉树到达对应节点，将其计数器加一，若比当前最大重复还大，则更新当前最大。当然同时这也是一个建树的过程，如果第一次遇到就建立路径了。
相信中国人名字都不长，平均长度为3个汉字吧，则访问该树的平均深度为3*16 = 48，常数级。
复杂度分析： 时间复杂度 O(n) ,这里n为中国人的名字总个数；
空间复杂度，一棵深度不大的树而已，不会超过 2^m ，这里m为最大二进制位串长，即最大深度。
假设汉字编码为GB2312十六进制编码，那么一个名字在计算机内存储表示为一系列的二进制位。譬如 “张三“，应当是一个32位的二进制位串，“张三丰”应当是一个48位的二进制位串。由于编码严格，所以名字不同，编码绝对不同。
算法思想：
建立一棵二叉树，类似哈夫曼编码树，遇0转向左子树，遇1转向右子树。每个节点设置一个计数器 count, 保存从根节点到该节点路径所代表的位串（其实代表一个名字）的重复次数。
对于每个名字，转化为位串，沿二叉树到达对应节点，将其计数器加一，若比当前最大重复还大，则更新当前最大。当然同时这也是一个建树的过程，如果第一次遇到就建立路径了。
相信中国人名字都不长，平均长度为3个汉字吧，则访问该树的平均深度为3*16 = 48，常数级。
复杂度分析： 时间复杂度 O(n) ,这里n为中国人的名字总个数；
空间复杂度，一棵深度不大的树而已，不会超过 2^m ，这里m为最大二进制位串长，即最大深度。
syy6 2007-11-13
- 打赏
- 举报
谁知道。
我投的职位压根不是搜索方面的。
我投的职位压根不是搜索方面的。
yeetoo 2007-11-13
- 打赏
- 举报
3楼的算法很正确, 现在的公司怎么出题都出海量数据的处理算法了, 这分明的搜索引擎的招聘题目.
lhrj 2007-11-13
- 打赏
- 举报
让他们把13亿人全录入数据库中再说.
medie2005 2007-11-11
- 打赏
- 举报
但是名不常用的汉字非常多。
=====================
用不常用字来做名的多吗？别忘了中国国情：农村人口可是占很大部分，他们可不会用那种自己都不会念的字做儿女的名字。
=====================
用不常用字来做名的多吗？别忘了中国国情：农村人口可是占很大部分，他们可不会用那种自己都不会念的字做儿女的名字。
zwb521 2007-11-11
- 打赏
- 举报
不知道
用分类汇总不知行不
好像数据量很大哦
学习
用分类汇总不知行不
好像数据量很大哦
学习
syy6 2007-11-11
- 打赏
- 举报
个人主要觉得有些假设不一定成立，
例如姓一般是常用汉字，但是名不常用的汉字非常多。
而且很多假设很难避免一个极端情况，就是三个字的名字，罕见字名字重复多。
虽然依照现有的统计数据，应该极端情况不成立，但是直接排除，理由未必充足。
例如姓一般是常用汉字，但是名不常用的汉字非常多。
而且很多假设很难避免一个极端情况，就是三个字的名字，罕见字名字重复多。
虽然依照现有的统计数据，应该极端情况不成立，但是直接排除，理由未必充足。
medie2005 2007-11-11
- 打赏
- 举报
GB 2312-80 把收录的汉字分成两级。第一级汉字是常用汉字，计 3755 个，置于16～55区，按汉语拼音字母／笔形顺序排列
GB 2312－80 图形字符代码表
01-07区 08-15区 16-23区 24-31区 32-39区 40-47区
48-55区 56-63区 64-71区 72-79区 80-87区 88区以下略
结合汉字编码表，可以设计一个算法来解决问题。
因为名字一般是常用汉字，所以在剩下的按姓氏分的名字中，由于同一个文件姓一样，所以同一个文件中的名只能有3755*3755种可能，为方便计算，我们将它放大为4096*4096，因此，可以开一个长度为 4096*4096 Hash表：
int Hash[4096*4096]，每一个可能的名字对应着表的一个下标索引。
对每一个姓文件，都进行如下操作：
开始时将Hash[]全部清零。
然后就开始扫描，将每个名字转化为一个数字index，++Hash[index]。
最后，在Hash[]中找到最大者及其对应的下标索引k就可以了，那么，在这个姓中出现次数最多的名，可以由下标索引k得到。
空间要求是4096*4096*4=16777216*4=64M，不算太大。
GB 2312－80 图形字符代码表
01-07区 08-15区 16-23区 24-31区 32-39区 40-47区
48-55区 56-63区 64-71区 72-79区 80-87区 88区以下略
结合汉字编码表，可以设计一个算法来解决问题。
因为名字一般是常用汉字，所以在剩下的按姓氏分的名字中，由于同一个文件姓一样，所以同一个文件中的名只能有3755*3755种可能，为方便计算，我们将它放大为4096*4096，因此，可以开一个长度为 4096*4096 Hash表：
int Hash[4096*4096]，每一个可能的名字对应着表的一个下标索引。
对每一个姓文件，都进行如下操作：
开始时将Hash[]全部清零。
然后就开始扫描，将每个名字转化为一个数字index，++Hash[index]。
最后，在Hash[]中找到最大者及其对应的下标索引k就可以了，那么，在这个姓中出现次数最多的名，可以由下标索引k得到。
空间要求是4096*4096*4=16777216*4=64M，不算太大。
medie2005 2007-11-11
- 打赏
- 举报
首先，排除那些长度大于3的名字，因为生活中最常见的名字是2个字或3个字的，长度大于3的名字不常见。
然后，从姓分析。
最常见的名字的姓必然在百家姓中排名靠前，因此只要考虑名字的姓以百家姓中的就可以了。
然后考虑其他的。
找一些名字中的常用字，这些字基本上都是好字，数量不会很多，并将这些字建一个Hash表（按汉字编码来hash，若这个字是好字，那么将对应位置置1，否则置0）。
扫一遍全国人民的名字，分析其中的姓是否在百家姓中、名字中的字是否是好字。若两个条件满足，则按姓氏留下该名字（即同姓的放在一个文件中），否则，剔除该名字。
剩下的就比较麻烦了，还没想好。
然后，从姓分析。
最常见的名字的姓必然在百家姓中排名靠前，因此只要考虑名字的姓以百家姓中的就可以了。
然后考虑其他的。
找一些名字中的常用字，这些字基本上都是好字，数量不会很多，并将这些字建一个Hash表（按汉字编码来hash，若这个字是好字，那么将对应位置置1，否则置0）。
扫一遍全国人民的名字，分析其中的姓是否在百家姓中、名字中的字是否是好字。若两个条件满足，则按姓氏留下该名字（即同姓的放在一个文件中），否则，剔除该名字。
剩下的就比较麻烦了，还没想好。
bryantd 2007-11-11
- 打赏
- 举报
你可以这样回答：
将13亿中国人的名字存入数据库table_name(name varchar(100))
用SQl来执行：select max(static_table.count) as 'max_count' from (select name, count(name) as 'count' from table_name group by name) as static_table
看他怒不怒，哈哈！！
将13亿中国人的名字存入数据库table_name(name varchar(100))
用SQl来执行：select max(static_table.count) as 'max_count' from (select name, count(name) as 'count' from table_name group by name) as static_table
看他怒不怒，哈哈！！
