编程珠玑第二章问题A 编程珠玑适合什么人看

题目:给定一个包含40亿个随机排列的顺序文件,找到一个不在文件中的32位整数,在有足够内存的情况下应该如何解决该问题?如果有几个外部的临时文件可用,但是仅有几百字节的内存,又该如何解决?

(1)对于有足够内存的情况,完全可以采用位图存储的方法,详细内容看《编程珠玑》第一章。

(2)Ed Reingold 给出了另外一种解法。


 问题的关键是只要找到一个数字,那么我们把问题简化一下,给定一个文件,里头最多包含16个4bit的整数,找到一个不在文件中的4bit整数。假设这十个数是12 3 4 5 7 6 9 8 10。
  取出一个数字,如果是最高位为1,放到一个文件中,否则放到另外一个文件中。同时用两个计数器记录这两个文件中的数字个数。最高位为1或0的4bit数字有都只有8个。所以如果其中有一个文件(也可能两个都是)分过去的个数小于8个,那么遗漏的数字肯定在这个文件的这堆数字里头。
  
  高位为0, 1 2 3 4 5 6 7
  高位为1, 8 9 10
  
  高位为0的数字是7个,高位为1的数字个数为3个,显然这两堆都遗漏了数字(比如第一堆遗漏了0), 如果有重复的数字,那么也有可能其中的一堆数字个数多余8,那么另外一堆肯定少于8
  选择数字个数少的那一堆,如此再继续区分第二高位为1跟为0的……以此类推,最后就找到了那个遗漏的数据

如果有重复的数据怎么办,假设数据是9个7,一个8? 比如第一次找, 高位为0,7 7 7 7 7 7 7 7 7 高位为1,8 那选择个数少于16/2=8的那组数据继续就能找到,这里对第二堆数据(只有8,说明高位为1的只有一个数)很快就找到了9,10,11,12,13,14,15都是缺失的。
编程珠玑第二章问题A 编程珠玑适合什么人看

  

爱华网本文地址 » http://www.413yy.cn/a/25101013/157190.html

更多阅读

巫师1第二章攻略 《职场章鱼哥》第二章(1)

第二章  如何得到老板的赏识第一节  初入职场的困惑前不久,我将之前网友发来的问题整理了一下,发现很大一部分是工作时间不长的网友发给我的。其中,问题最集中的是自己在办公室里不受重视或者老板不懂得欣赏自己的“美”,进而感觉

高二化学选修4第二章 《向宝洁学什么》第二章(二)

系列专题:《向宝洁学什么》 第三节 让别人记住你的四个原则 宝洁经典案例象牙香皂的“品质联想”象牙香皂的名称由来是一个很有趣的故事。在象牙香皂诞生的年代,人们的品牌意识几乎为零。各家生产的肥皂普遍叫做“肥皂”,已经萌

第23节:第二章 处世之道:一听二看三点头(12)

系列专题:《做人做事好方法》  从这个例子可以看出,要巧妙地拒绝就应该做到:  (1)让对方了解实际情况和难处,开诚布公地拒绝,使对方相信你的真诚。  (2)要给对方留下面子,切不能伤人自尊。别人之所以来你这里求职,一方面是看好你公司的

声明:《编程珠玑第二章问题A 编程珠玑适合什么人看》为网友走近你分享!如侵犯到您的合法权益请联系我们删除