《编程珠玑》笔记（第01-05章）

• 第1章 开篇
• 第2章 啊哈！算法
• 第3章 数据决定程序结构

第1章 开篇

书籍：

• 啊哈！灵机一动；
• software requirements & specifications [by Michael Jackson]；
• Conceptual blockbusting [by James L.Adams]。

第2章 啊哈！算法

1. 给定一个最多含40亿个32位整数的文件，找出一个不在文件中的32位整数。
   • 解：可以通过写新文件做到O(n)，因为每次只需处理少的那一半。
2. 扩展：给定的是一个内存中的数组而不是文件。
   • 解：用快排的partition思想，设当前数组最大值为max，最小值为min，则用(max-min)/2作为pivot来分割。
3. 给定包含43亿个32位整数的顺序文件，找到一个至少出现2次的整数。
   • 解：
     • 如果刚开始时文件（数组）中的数的个数多于max-min+1（本题这个假设为真因为2^32<4,300,000,000），那么可以这么做：用partition思想，每次把当前区间一分为二，每次找数多的那一半递归。设数多的那一半最大值为max，最小值为min，则只需取max-min+2个数进行递归即可。
     • 否则，如果题目保证至少有一个数重复，平均情况下可以用桶：共n个桶（n为数的个数），把数t放进桶n(t-min)/(max-min+1)中，然后继续做：如果数最多那个桶满足上述条件就用上述解法，否则继续分桶。

   问：极端情况下，譬如数组1, 2, 3, ..., 9999, 10000, 1000000000，怎么做？哈希？有确定性O(n)算法吗？

第3章 数据决定程序结构

1. 做程序设计时用到的几条原则
   • 使用数组重新编写重复代码
   • 封装复杂结构
   • 尽可能使用高级工具
   • 从数据中得出程序的结构
2. 书籍：
   • rapid development
   • software project survived guide