趣题——排序（1）
浏览数：19 /
时间：2015年06月08日
题目
给定一个最多包含40亿个随机排列的无符号32位整数的顺序文件，找出一个不在文件中的32位整数（文件中一定至少缺失一个这样的数）。在具有足够内存的情况下，如何解决该问题？如果有几个外部的临时文件可用，但是仅仅有几百字节的内存，又该如何解决该问题？
思路（仅考虑单机情况）
关于括号的提示——文件中一定至少缺失一个这样的数： 一个无符号32位的整数的最大为
232 ,即4294967296个这样的数。因此，如果有重复，则实际的数量更小于40亿；如果没有重复，则仍然缺少294967296个这样的数。当内存足够时，可以使用
232 位的位向量（224 字节）来标记对应位置上的数字是否存在，若存在则使用1，否则标0。然后顺序扫一遍向量，找到一个标0的即可。当内存不足时，仅有几个外部的临时文件和几百字节的内存可用，那么，我们考虑二分的思想，如果之前存在缺失的数字，则二分之后我们需要的那一部分仍然 存在缺失的数字。我们可以按照最高位进行二分（分1和0）；二分之后，理论上来说单个数量最大为20亿，若小于20亿，则一定存在缺失的数字。然后针对该部分继续进行二分，只不过是针对次高位上的进行二分即可；直到得到几百字节的大小的一部分，放入内存，顺序扫描得到缺失的数字即可。
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
