编程珠玑笔记(2)–啊哈!算法(I)

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

  • 解答
  •   我们从表示每个整数的32[……]

    Read more

    编程珠玑笔记(1)–开篇

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

    Read more