|
|
腾讯笔试题一则* x& u3 [% G9 b3 v$ Y
3 V, C6 _& A# H: t7 ^0 j
一个文件中有40亿个整数，每个整数为四个字节，内存为1GB，写出一个算法：求出这个文件里的整数里不包含的一个整数" W- e5 {3 |- M( o
答:: [6 K$ e/ E0 x; n7 R* z
方法一: 4个字节表示的整数，总共只有2^32约等于4G个可能。0 B+ x4 I% b1 q4 o7 T% D3 n
为了简单起见，可以假设都是无符号整数。
% l! o7 w! e- h分配500MB内存，每一bit代表一个整数，刚好可以表示完4个字节的整数，初始值为0。基本思想每读入一个数，就把它对应的bit位置为１，处理完40G个数后，对500M的内存遍历，找出一个bit为0的位，输出对应的整数就是未出现的。算法流程：' w: ^1 Y4 k* K* r9 ?
１）分配５００ＭＢ内存buf，初始化为０- B0 X' z1 V, ?! q5 ]
２）unsigned int x=0
( n9 F4 x0 E/ `' e4 t, u7 L9 u; n! g; D8 L$ Q
腾讯2010实习生招聘笔试题（全套）：http://bbs.aftjob.com/thread-606605-1-1.html9 [- z0 r) ?( W2 ?
2011年名企薪酬信息专版：http://bbs.aftjob.com/forum-37-1.html
6 m- R- ~+ a$ d! M' X' f腾讯求职俱乐部：http://bbs.aftjob.com/group-47-1.html |
|
IP卡
狗仔卡
发表于 2012-4-12 16:34
提升卡
置顶卡
沉默卡
喧嚣卡
变色卡
显身卡
