摩根士丹利IT笔试题求教,该怎么处理
摩根士丹利IT笔试题求教昨天校园招聘的题目原题目为英文在磁盘上有一个文件，里面只含有（2的32次方-1）个数
摩根士丹利IT笔试题求教
昨天校园招聘的题目
原题目为英文
在磁盘上有一个文件，里面只含有（2的32次方-1）个数字，每个数字都是处于[0,2的32次方]之间。
但是可以使用的内存仅仅有数百K字节左右。
请使用任何一种编程语言(伪代码也行)，找出任意一个属于[0,2的32次方]之间并且没有在这个文件中出现数字。
想请教下大家，有没有较好的解法，谢谢！
[解决办法]
我想了一个算法，两次扫描文件中的数据即可得到结果。
如下：
开一个unsigned int count[0..0xFFFF] 的数组。需要65535 * 4 / 1024 = 252KB的内存。
初始化为0.
然后做一次扫描，每读一个数字K，则其低字的计数器加一，即： count[ k & 0xFFFF ] ++;
扫描完整个文件之后，至少会有一个计数器的值小于 0x10000，说明这个低字等于该值的数字至少有一个没有出现。
记下该值，设为low
然后再次将count数组清0。再做第二次扫描，对于每一个数字K，先判断其低字是否等于 low ，若等于，则将其高字的计数器加一，即： count[ k >> 16 ]++;
然后再扫描一遍count数组，只要是count[i] == 0的，就说明高字为i ,且低字为low的数字没出现过。
此时 (i << 16) | low 为所求。
[解决办法]
位图需要
2^32 / 8 bytes = 4GB / 8 = 512 MB 内存。
题目要求几百KB。
[解决办法]不知道你翻译得对不对，不过一般情况下是说这个文件里每个数字都是唯一的，且只有一个数字（不是你说的任意一个）少了，这样只要把所有数求和，就可以算出哪个数少了
[解决办法]低字为0有很多个的话，看其计数器到底有多少个。
如果其计数器小于 0x10000 ，那必然至少有一个低字为0的数字没出现过。
若其计数器大于等于 0x10000,则不选这一个低字，选其他的小于0x10000的。
根据抽屉原理可以证明，至少有一个计数器会小于0x10000。
[解决办法]另附上数学证明：
1.2^32-1 个数字 放入2^16个桶中，至少有1个桶中的数字个数小于 (2^32) / (2^16) 即：0x10000。
证明：
用反证法，假设不存任何一个桶中的数字个数小于 2^16 ,即每一个桶中的数字的个数都大于等于2^16。
那么其所有的数字的个数 大于等于 2^16 * 桶数 即 2^16 * 2^16 = 2^32 。这与命题相违背，因此结论得证。
2.对于任何一个低字为low，且数字的个数小于0x10000的数字序列。都至少存在一个低字为low，且不在该数字序列中的数字。
证明：
这是显而易见的。低字为low的所有32位数字总共有2^32 / 2^16 = 0x10000个。而这个数字序列的个数小于0x10000，所以必然会有一个低字为low的数字不存于该序列。
这样就证明了算法的正确性。若有疑问，请跟帖。
[解决办法]文件的话，1楼的方法可以。
[解决办法]1L的方法不错
[解决办法]要是我去做，也许会用一个bitmask文件，文件的每个4字节，记录对应的整数出现的次数:)
