月度归档：2013年09月

编程珠玑笔记（2）–啊哈！算法（I）

发表于由
回复
  • 问题A

    • 　　给定一个最多包含40亿个随机排列的32位整数的顺序文件，找出一个不在文件中的32位整数（在文件中至少缺失一个这样的整数）。在具有足够内存的情况下，如何解决该问题？如果有几个外部的“临时”文件可用，但是仅有几百字节的内存，又该如何解决该问题？

  • 解答

    • 　　我们从表示每个整数的32位的视角来[……]

    Read more

    编程珠玑笔记（1）–开篇

    发表于由
    回复
  • 作者在书中经过与友人的讨论后对问题的准确描述
      • 输入：一个最多包含n个正整数的文件，每个数都小于n，其中n=107。如果在输入文件中有任何整数重复出现就是致命错误。没有其他数据与该整数相关联。
      输出：按升序排列的输入整数的列表。
      约束：最多有（大约）1MB的内存空间可用，有充足的磁盘存储空间可用。[……]

    Read more