39个答案 按时间排序 按投票排序

2 0

将电话号码转为数值型
数值代表位图的偏移量

创建一个100,000,000/8+1大小的byte数组作为位图

num/8表示偏移量
num%8表示在该byte的第几位

如果该位是0，置为1
如果是1，已经重复

2012年6月04日 23:15

神鬼泣
36
0 0 1

• 3条评论

1 0

假设电话号码是8位的（有些城市是7位的，如果带区号的话自己根据这个思想做变换即可）

那么不管存在不存在，所有的电话号码一共有10^8个

建立一个int类型的数组，数组大小为3125000，共需要不到12M的内存

可以存储10^8个布尔类型的值（一个int占32位，没一位相当于一个布尔值），每个布尔类型的值对应一个号码，初始化的时候让数组里的每个值都为0

也就是说现在数组里所有的布尔值都为false

然后从文件里读出第一个号码，假设号码是00000001，那么就将数组里第0个值的第二位设置为1，也就将这个号码标识为存在，下次再读入时就根据标识判断是否重复


说简单点，就相当于你将10^8个二进制数排队站着，然后将所有的电话号码排队站着，把他们看成是一对一的关系，如果一个号码发现自己的位置被比人占了，那么这个号码一定是重复的

当然因为电话号码并不可能是00000001，所以可以针对电话号码的情况做一些优化，而不必要申请3125000个int大小的内存。

2012年6月04日 18:19

kuangren
23
0 0 1

• 3条评论

1 0

有几个方案：
Bloom Filter

Trie Tree

文件多路归并排序

自己百度或者请人做吧

2012年6月04日 16:47

chen_yongkai
1600
1 1 23

• 2条评论

1 0

多文件，排序，去重，也是个选择！

2012年6月04日 16:24

cmyx2008love
215
0 0 10

• 添加评论

1 0

将所有号码分类在多个文件里嘛，比如说号码有八位，前四位相同存放在一个文件

2012年6月04日 15:16

magicfow
33
0 0 0

• 添加评论

0 0

   可以考虑使用二个BitSet（长度为电话号码的最大值）设为bitSet1,bitSet2,利用clear()将所有位都置为false。
   读取一个电话号码后（先读入多条记录到缓冲区），判断其数值对应bitSet1位置，若为false,则置为true，否则将bitSet2中相应位置置为true,以此类推……
   所有电话号码处理完后，bitSet2中的为true的位置即为重复的电话号码。

   祝好！

2012年9月07日 17:41

shutear
25
0 0 0

• 添加评论

0 0

不用数据库的话，可以参考BitSet的思路，自己设计一个类似的位序列bucket，根据号码映射到位序列中，置位 ，保证不同的号码映射到不同的位置就行了，可以对号码做个优化处理或者位序列够大就行

2012年9月05日 10:38

husan_3
4
0 0 11

• 添加评论

0 0

《编程珠玑》中有这个算法

2012年9月03日 17:17

crawler
25
0 0 0

• 添加评论

0 0

一般都是导入数据库再update telcode= trim(telcode);
然后再select distinct telcode from table_name;

2012年8月29日 11:08

wang1352083
30
0 0 1

• 添加评论

0 0

你知道berkeleydb嵌入式数据库吗？从数据结构的角度来看那就是一个哈希表，而且它还有个优点是随时和硬盘相联系的，这样你的数据再多也不用担心内存溢出问题，或者用布隆过滤器一样可以解决的

2012年8月15日 16:56

zhangjiugang
15
0 0 2

• 添加评论

0 0

大数据处理，可以参考hadoop的设计

2012年7月11日 16:19

liaosifa
28
0 0 4

• 添加评论

0 0

放到数据库里       ，一个sql就搞定了

2012年7月09日 12:36

YH555
30
0 0 1

• 添加评论

0 0

布隆过滤器

2012年6月26日 18:13

rinapt
31
0 0 0

• 添加评论

0 0

Bloom Filter

文件多路归并排序

tire 树 估计内存放不下


但是可以考虑前6位trie树 后面文件

BloomFilter是最简单的..但是不一定准确

如果我做..我选择归排序吧...

2012年6月21日 11:18

ansjsun
129
0 1 5

• 添加评论

0 0

http://developer.51cto.com/art/201206/343690.htm
Java中用内存映射处理大文件

2012年6月21日 08:59

blueram
188
0 1 4

• 添加评论

0 0

根据号码的前1位或两位来切分文件，文件切的够小，那你在插入到新的文件中的时候，就可以在有限的内存中排除重复的数据了。

2012年6月21日 00:19

卒子99
56
0 0 0

• 添加评论

0 0

这个问题有两个棘手的地方：
1、这个100w条号码文件肯定不能一次读到内存中来的，应该分片段读取，方法是什么？
利用java.nio中的内存映射文件可以分段读取数据与处理数据，可以解决java.io中对大文件处理的不足。

2、接着上一步分段读取到内存中来之后，肯定不能放内存中，应该将刚读好的数据片段立即转移到其他存储介质中，以释放内存空间，否则这就和一次性读到内存没什么差别了，这里可以根据需要可以选择传统的关系数据库如MySQL和K-V数据库如Redis等等(后者属于NOSQLk-v型数据库,IO性能极高，做count也很容易)

2012年6月06日 13:34

penggle
30
0 0 1

• 添加评论

0 0

Bloom过滤应该可以解决！

2012年6月06日 13:08

wiki_more
2
0 0 5

• 添加评论

0 0

《编程珠玑》就在开篇里边讲了一个类似问题的精妙解答，具体算法我要在里说的话，就显得卖弄了。呵呵。

2012年6月06日 09:37

guazi
454
0 0 14

• 添加评论

0 0

《编程珠玑》上对这个问题有精彩的解答。推荐你看看

http://ishare.iask.sina.com.cn/f/13310338.html

2012年6月06日 09:31

guazi
454
0 0 14

• 添加评论

0 0

hashMap是个不错的思路，根据内存决定一次读入内存多少数据，key为号码，value为出现次数，若hashmap里已经有了该号码，则value+1,

2012年6月06日 09:00

zyn010101
2795
2 3 156

• 1条评论

0 0

存入数据库再进行处理此方法确实不错。数组排序我不大赞同，哈希集合不过倒是可以考虑。

2012年6月06日 08:59

itlangqun
45
0 0 4

• 添加评论

0 0

不是做数据库的，只说一下我的想法：
1.将100万电话按照前两位进行分组，例如18*****、15*****、19*****分组
2.对每个分组内电话号码进行去重操作（现在内存能跑的开了吧）

2012年6月06日 08:55

ivoter
30
0 0 1

• 1条评论

0 0

考DS的问题，好题

2012年6月05日 14:18

softpower
30
0 0 0

• 添加评论

0 0

才100W电话号 直接放内存里跑。

2012年6月05日 13:49

DDT_123456
30
0 0 0

• 5条评论

0 0

解决方案:

一.借助数据库
1.先分割成几个一定大小文件,使用多线程(可选)再将一个个小文件导入到一张表中
2.使用order by 电话号码
3.统计数据库总行 - 再使用"distinct"去重复=重复的行数

二.使用google
将其做成一个网页,再使用"google自定义搜索"ok(有计数功能)

三.使用Apache lucene全文检索

2012年6月05日 12:39

潘清山
58
0 0 5

• 添加评论

0 0

这个命题有点像电信计费系统从交换机上去下载二进制文件，然后根据文件中的数据进行用户计费的。

如果是相似需求的话，可以找一找相关计费资料看看的，那个计费效率很高的。

2012年6月05日 11:58

mymailzxj
153
0 0 3

• 添加评论

0 0

如果电话号码包括手机号，或者带有区号呢？
就有11位，12位，8位。。。。。。

2012年6月05日 10:13

chen_yongkai
1600
1 1 23

• 1条评论

0 0

linux下sort和uniq命令

2012年6月05日 10:04

poston
30
0 0 1

• 2条评论

0 0

hash->boolean 滤波器

2012年6月05日 10:01

homepagea
30
0 0 0

• 添加评论

0 0

玩过map-reduce的话，做这个题应该是没问题！

简单处理：对文件进行分片(N)，  hash code % N -->分发到不同的reduce，这样相同号码肯定在一个reduce中

2012年6月05日 09:53

wzju64676266
0
0 0 0

• 2条评论

0 0

100万条，存到数据库里做查询也并不夸张嘛！

2012年6月05日 08:37

xxmc01
30
0 0 0

• 1条评论

0 0

根据你计算机的运算能力，把电话号码比如说以前3位为过滤分组依据，可把一个大文件分为最多999个小文件，小文件内大概平均也就是1000个电话号，顶多也就是8位-3位=5位，也就是说所分的这些小文件里，最大的极限值，也就是99999个电话号码，在内存是不成问题的，这也就解决了内存不足的问题，至于怎么去筛选，自己想把

2012年6月05日 01:01

xds2008
30
0 0 1

• 添加评论

0 0

定义int二维数组，电话号码前4位作一维数组下标，4位后面的做二维下标，相同号码在对应下标数组值加1，二次循环就能完全找出重复号码个数，重复次数      除了占CUP外，内存占用相当少

2012年6月05日 00:14

zhoutao_0116
30
0 0 0

• 添加评论

0 0

归类再进行分析，

2012年6月04日 20:21

jyjava
32
0 0 1

• 添加评论

0 0

假设电话号码是8位的（有些城市是7位的，如果带区号的话自己根据这个思想做变换即可）

那么不管存在不存在，所有的电话号码一共有10^8个

建立一个int类型的数组，数组大小为3125000，共需要不到12M的内存

可以存储10^8个布尔类型的值（一个int占32位，没一位相当于一个布尔值），每个布尔类型的值对应一个号码，初始化的时候让数组里的每个值都为0

也就是说现在数组里所有的布尔值都为false

然后从文件里读出第一个号码，假设号码是00000001，那么就将数组里第0个值的第二位设置为1，也就将这个号码标识为存在，下次再读入时就根据标识判断是否重复


说简单点，就相当于你将10^8个二进制数排队站着，然后将所有的电话号码排队站着，把他们看成是一对一的关系，如果一个号码发现自己的位置被比人占了，那么这个号码一定是重复的

当然因为电话号码并不可能是00000001，所以可以针对电话号码的情况做一些优化，而不必要申请3125000个int大小的内存。

2012年6月04日 18:17

kuangren
23
0 0 1

• 添加评论

0 0

思路：多线程利用map->reduce算法
分片：
0.遍历文件，目的是“采样”，找到最大值和最小值，并且掌握数据的大概分布。
1.分割文件：将大文件分割为小文件。比如总共10G。分割为100个文件。每个文件100M
3.计算当前需要的线程数。比如总共数据10G。分割为100个文件。当前可用内存为1G。那么线程数据数就是10（1G/100M).需要处理10轮。
map：
4.每个线程遍历分割后的数据，按照采样点将其保持到不同的输出文件中。
reduce
5.依次遍历所有输出文件。找出相同的数据。

2012年6月04日 17:52

wangxin0072000
475
0 0 0

• 3条评论

1 1

先把号码 存到数据库里，然后再查询，一个sql就搞掂了。

2012年6月04日 16:08

xiongjinpeng
27
0 0 1

• 4条评论

1 2

楼上的本来是我要说的，可是系统让我做什么答题小测试。。。。就让你说了。很赞同你说的。另外你说话言简意赅，值得学习

2012年6月04日 16:28

大鱼没睡
31
0 0 1

• 2条评论