您的位置：程序门 -> 专题开发/技术/项目 -> 数据结构与算法

腾讯笔试题

[收藏此页] [打印本页]选择字色：背景色：字体：[大][中][小]

腾讯笔试题

发表于：2007-10-14 13:02:43 楼主

一个文件中有40亿个整数，每个整数为四个字节，内存为1gb，写出一个算法：求出这个文件里的整数里不包含的一个整数

发表于：2007-10-14 14:10:391楼得分:0

4个字节表示的整数，总共只有2^32约等于4g个可能。
为了简单起见，可以假设都是无符号整数。
分配500mb内存，每一bit代表一个整数，刚好可以表示完4个字节的整数，初始值为0。基本思想每读入一个数，就把它对应的bit位置为１，处理完40g个数后，对500m的内存遍历，找出一个bit为0的位，输出对应的整数就是未出现的。
算法流程：
１）分配５００ｍｂ内存buf，初始化为０
２）unsigned int x=0x1;
for each int j in file
buf=buf ¦x < <j;
end
（3) for（unsigned int i=0; i <= 0xffffffff; i++)
if （!（buf & x < <i))
{
output（i);
break;
}
以上只是针对无符号的，有符号的整数可以依此类推。

发表于：2007-10-14 14:50:362楼得分:0

楼上的思想我都领会了，但是这个含有40亿个整数的文件太大了，读入内存会溢出啊！怎么解决，是分块吗？

发表于：2007-10-14 20:05:233楼得分:0

文件可以分段读啊，这个是o（2n）算法，应该是很快的了，而且空间也允许的。
不过还可以构造更快的方法的，更快的方法主要是针对定位输出的整数优化算法。
思路大概是这样的，把值空间等分成若干个值段，比如值为无符号数，则
00000000h-00000fffh
00001000h-00001fffh
......
0000f000h-0000ffffh
.....
fffff000h-ffffffffh
这样可以订立一个规则，在一个值段范围内的数第一次出现时，对应值段指示值xn=xn+1，如果该值段的所有整数都出现过，则xn=1000h，这样后面输出定位时就可以直接跳过这个值段了，因为题目仅仅要求输出一个，这样可以大大减少后面对标志数值的遍历步骤。
理论上值段的划分有一定的算法可以快速的实现，比如利用位运算直接定位值段对应值进行计算。

发表于：2007-10-14 20:49:234楼得分:0

楼上的回答好

发表于：2007-10-15 09:19:375楼得分:0

发表于：2007-10-15 15:10:096楼得分:0

1楼的做法很好。至于读取文件可以只申请一个整数单元的空间就行了，一个一个的读，又不是一次把所有读进内存。
至于读取文件的函数怎么关联到外存文件，操作系统会帮我们解决的。

发表于：2007-10-25 15:11:127楼得分:0

1楼结合6楼的算法应该是可行的，但512m的内存如何以位为单元来寻址？我的想法是：
假设分配的内存从begin开始，先以8-bit为单位寻址，再以1-bit为单位，例如整数x就由
（begin + x/8) ¦= （1 < < x%8) 来标志。

下一篇：从10亿条整数中，选择出现次数最多的100个整数
上一篇：数据结构和算法的关系

其他资讯