《编程珠玑》第一章读书笔记

记得第一次拿起这本是在06年，那时还是大二呢，呵呵。在图书馆看到了这本书，信手翻了翻，郁闷的是没看懂啊。时隔多年再次拿起这本书，自己有了更好的底子，慢慢看，也可以看懂啦~

正如第一章标题所说的，这章是个开题。不过一上来就抛出了个算法设计题，还对时间空间复杂度都有要求。

题目是这样的：

一个最多包含n个不重复的正整数的文件，每个数都小于10⁷。要求对这些数进行排序，且只有大约1MB的空间可用。

书中给出的算法如下。

由于最多只有1000万个数，且这些数不重复，故可考虑用位图或位向量的方法。

使用一个具有1000万个位的字符串表示这些数：当整数i在文件中存在时，字符串的第i位为1。这样，1000万个位约占1.19MB，符合题目对空间的要求。程序的伪代码如下：

/*1. 设置所有的位为0*/

for i = [0, n)

bit[n] = 0;

/*2. 若文件中存在整数i，设置第i位为1*/

for 文件中所有整数i

bit[i] = 1;

/*3. 根据字符串的位，依次输出整数*/

for i = [0, n)

if bit[i] == 1

output

就是以上三步曲。思想挺简单的，也很节约空间。不过，如果一次只从文件读入一个数的话，做了1000万次的读入操作，会不会很耗时间？这里先打个问号。另外，该方法充分利用了题目的数的特点，不重复，若不满足这个条件，还得先做些处理。第一章习题中对此有涉及。

后记：

实际上，只需要读入一次文件即可，打开文件后，不断读入文件中的每个整数，应该不用花太多的时间。