算法问题

fanki

之前有人问我一题，是面试官问的。
是查找题
有40亿个数据，你的电脑只有4G内存，如何高效的从一大堆数据中找出那个是重复的数据，不考虑类型，和其他东西
只考虑算法
方法一是：两两对比直到找到~~这是最低效效率的，时间复杂的n平方。（这应该是不行的）
方法二是：把数据读到map中读到重复返回，这个有个问题是只有4g，如果分段的话可以实现，可是如果那个重复的数字跨度超过4g的数据，那这个方法就不行了（只能扩大内存，通过用内存来提高效率）

面试官还说有更好的方法？我暂时想不到了，希望大家可以帮帮手，一起学习学习~~

如果题目说的不太清楚我再解释一下~~表达不好，多多见谅。

张唯

就两两对比，按照统一顺序分成若干段，同时进行对比，分的段数越多，需要的时间越少。同时进行分类对比，分类的层次越多，需要的时间越少。:dizzy:

编程难

如何高效的从一大堆数据中找出那个是重复的数据？
这堆数据只有一组重复的吗？还是会有一堆，只找出一组就行了。这数据是神马数据？整数？如果是整数那么用hash就可以了

fanki

编程难 发表于 2013-7-24 13:06

                               
登录/注册后可看大图

如何高效的从一大堆数据中找出那个是重复的数据？
这堆数据只有一组重复的吗？还是会有一堆，只找出一组就 ...

只有一组重复~~
就像1 2 3 5 4 8 9 7 8 48 68 59 15 35 46 49 。。。。。。 46 中间一直没有重复
就46 和 46 重复了。
hash是怎么弄？{:7_155:}谢谢吖！！

编程难

fanki 发表于 2013-7-24 13:28

                               
登录/注册后可看大图

只有一组重复~~
就像1 2 3 5 4 8 9 7 8 48 68 59 15 35 46 49 。。。。。。 46 中间一直没有重复
就46  ...

是整数吗？？？？或者范围比整数更小也可以

编程难

弄个超大的数组byte hash_table[0xffffffff], 清零，然后循环遍历这40亿个数，比如遍历到的数是100，那么就先判断hash_table[99]是否是0，如果是0则说明第一次出现，就把其位置1，如果非零则说明之前出现过，那么就是重复的数字了。思路就是这样

tsembrace

数据无规律排列的话，怎么着也得遍历一次啊

fanki

编程难 发表于 2013-7-24 13:42

                               
登录/注册后可看大图

是整数吗？？？？或者范围比整数更小也可以

面试官说是可以当整数来处理。
他就没有告诉我最好的方法，就给我们自己思考的机会~~
我想了好久~~可是就没有想到什么更好的方法了~~
面试官说如果有比较多的项目经验应该会的。
我表示。。。。~~哈哈~~

fanki

tsembrace 发表于 2013-7-24 14:20

                               
登录/注册后可看大图

数据无规律排列的话，怎么着也得遍历一次啊

是无序的~~所以用后来就想用map嘛~~把他排排序~~方便查找，可是数据太多~~4g不够放~~所以面试那个人还问还有没有更好的办法~~我就想想想，可是没有想出来~~

pcfate

暂时想不到哎。。

fanki

pcfate 发表于 2013-7-24 16:36

                               
登录/注册后可看大图

暂时想不到哎。。

没事~~~先放一放~~有空再想~~嘻嘻~~谢谢哦~~

fanki

张唯 发表于 2013-8-4 22:49

                               
登录/注册后可看大图

就两两对比，按照统一顺序分成若干段，同时进行对比，分的段数越多，需要的时间越少。同时进行分类对比，分 ...

恩恩，这方法不错，我之前问了一下朋友~~他说好像可以用虚拟内存的~~我都不知道怎么弄~~还要努力学习呀~~一起加油！！