2 neqrhk NeQrhk 于 2016.01.19 21:01 提问

给定一个最多包含40亿个随机排列的32位整数的顺序文件,找出一个不在文件中的32位整数。

(在文件中至少缺失一个这样的数为什么?)括号里的话怎么得到的
在具有足够内存的情况下,如何解决该问题?
如果有几个外部的临时文件可以用,但是只有几百字节的内存,又该如何解决该问题。

3个回答

caozhy
caozhy   Ds   Rxr 2016.01.19 21:08

足够内存,用位图法。定义一个arr[4294967296]大小的数组,遍历顺序文件,遇到一个值,就把对应下标的置1,最后遍历这个数组,找0的元素。

caozhy
caozhy   Ds   Rxr 2016.01.19 21:09

如果只有几百的内存,可以用hashtable。不过位图只需要512M内存就可以了。

91program
91program   Ds   Rxr 2016.01.19 21:09
Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!
其他相关推荐
给定一个最多包含40亿个随机排列的32位整数的顺序文件,找出一个不在文件中的32位整数
给定一个最多包含40亿个随机排列的32位整数的顺序文件,找出一个不在文件中的32位整数。            1、在文件中至少存在这样一个数?            2、如果有足够的内存,如何处理?            3、如果内存不足,仅可以用文件来进行处理,如何处理? 答案:            1、32位整数,包括-2146473648~~2146473647,约42亿个整数
在一个包含40亿个随机排列的32位整数的顺序文件中(注意随机排序),找出一个不再文件中的32位整数
完整的题目: 在一个包含40亿个随机排列的32位整数的顺序文件中(注意随机排序),找出一个不再文件中的32位整数(即int类型的整数),文件中至少缺少一个这样的数  要求: 使用最少的内存,可使用外部的临时文件 思路: 将每个数转换为2进制数,然后进行0/1探测,将为0的位保存在一块内存中,将为1的位保存在另一块内存中, 一个文件中至多只有20亿个, 因为40亿小于2的32次方,所
40亿个随机排列整数问题
问题: 给定最多包含40亿个随机排列的32位整数的顺序文件,找出一个不在文件中的32位整数(在文件中至少缺失一个这样的数——为什么?)。在具有足够内存的情况下,如何解决该问题?如果有几个外部的“临时”文件可用,达十年后仅有几百字节的内存,又该如何解决? 解答: (1)如果具有足够的内存,可用采用位图法进行解决。需要2^32/8/1024/1024=512MB的内存。如果某个数在在文
编程珠玑之第二章questionA: 40亿个随机排列整数问题
问题描述: A. 给定一个最多包含40亿个随机排列的32位整数的顺序文件,找出一个不在文件中的32位整数(在文件中至少缺失这样一个数——为什么?)。在具有足够内存的情况下,如何解决该问题?如果有几个外部的“临时”文件可用,但是仅有几百字节的内存,又该如何解决该问题? 问题解析: 1、首先要明白整型代表的范围如下: 由此看出一个无符号长整型大约表示43亿个数,所以大约有3亿个数是在此
给定包含4300000000个32位整数的顺序文件,如何找出一个出现至少两次的整数
给定包含4300000000个32位整数的顺序文件,如何找出一个出现至少两次的整数 方法一:位向量标识 方法二:二分排序 由于4.3G>32位的整数空间,根据鸽笼原理,肯定会有重复的整数。搜索范围从所有的32位正整数开始(全部当成unsigned int,简化问题),即[0, 2^32),中间值即为2^31。然后遍历文件,如果小于2^31的整数个数大于N/2=2^31,则调整
面试题:给定一个包含4300000000个32位证书的顺序文件,求出一个至少包含两次的整数
<br />面试题:给定一个包含4300000000个32位整数的顺序文件,求出一个至少包含两次的整数。<br /> <br />思路:考虑两个条件<br />1. 所有的整数都存储在顺序文件中,因此,读取文件的次数将明显影响算法的效率<br />2. 顺序文件中包含的整数个数为4300000000,如果全部读取放在内存中的话,必须要考虑内存空间因素。<br /> <br />那么,有没有既节省时间又节省空间的solution呢?也就是,尽可能只顺序读取一次文件,并且采用尽可能少的内存的方法呢?<br />
一个文件中有40亿个整数,每个整数为四个字节,内存为1GB,写出一个算法:求出这个文件里的整数里不包含的一个整数。
4个字节表示的整数,总共只有2^32约等于4G个可能。 为了简单起见,可以假设都是无符号整数。 分配500MB内存,每一bit代表一个整数,刚好可以表示完4个字节的整数,初始值为0。基本思想每读入一个数,就把它对应的bit位置为1,处理完40G个数后,对500M的内存遍历,找出一个bit为0的位,输出对应的整数就是未出现的。 算法流程: 1)分配500MB内存buf,初始化为0
编程珠玑之第二章习题2
问题描述: 给定包含4 300 000 000个32位整数的顺序文件,如何找出一个至少出现两次的整数?  问题解析: 1、假设4 300 000 000个32整数的顺序是随机的。 2、给定的32位整数的个数是4 300 000 000大于2^32-1, 如果其中没有任何一个缺失的32整数,那么重复整数个数就是(4300000000-2^32+1)个。 3、可以通过统计中间值(2^32-1
新解:给定包含4 300 000 000个32位整数的顺序文件,如何找出一个至少出现两次的整数。
看了编程珠玑的这个问题,一看到是顺序已经排好,很多人会想到二分查找, 其实不然,线性搜索就可以做到。 /** * 问题描述: * 给定包含4 300 000 000个32位整数的顺序文件, * 如何找出一个至少出现两次的整数 * * @author Olive
有10亿个整数,要求选取重复次数最多的100个整数
转自:http://blog.163.com/tianshuai11@126/blog/static/618945432011101611414734/ 要解答这个问题,首先要弄清楚下面几个条件。  (1)有内存限制吗?  (2)整数的范围是多少?有符号,无符号,32位还是64位?  (3)整数集的内容大吗?(即出现的整数空间的大小大吗?)  (4)如果只需要求模糊解,怎么解?