习题9：
使用更多的空间来换取更少的运行时间存在一个问题：初始化空间本身需要消耗大量的时间。说明如何设计一种技术，在第一次访问向量的项时将其初始化为0.你的方案应该使用常量时间进行初始化和向量访问，使用的额外空间应正比于向量的大小。因为该方法通过进一步增加空间来减少初始化的时间，所以仅在空间很廉价，时间很宝贵且向量很稀疏的情况下才考虑使用。
分析：
计科同学应该知道，计算机系统优化时空间和时间难以得兼。空间换时间或者时间换空间是很常见的操作。
在空间换时间情形下，我们需要初始化更多的空间，这无形中增加了程序执行的时间。而这个题目的想法就是我们可不可以申请空间之后不用进行初始化操作，申请的空间就随它是随机值好了。后面我真正访问的时候再初始化，并且我第二次访问的时候我有办法知道它是不是已经被访问过。
OK，现在我假设真正存储数据的那个数组是data[]，现在我要访问某一个data[i]，然后使得这个值为0（根据题目要求），即：
data[i] = 0
那我下次再访问这个data[i]的时候是不清楚它之前有没有被访问过的。现在我们的一个简单的想法就是：把i给记录下来，这样不就知道data[i]之前有没有被访问过了吗。
说干就干，我们用一个数组to[]来记录所有已访问过的data[i]的下标i。比如我们依次访问data[]数组的i=1，5，3号的元素。data[1],data[5],data[3]按顺序被初始化为0，同时它们的下标1，5，3被记录在to数组中。
OK，现在我们如果再一次访问data[5]，我们通过查找to数组发现to数组中已经有5，说明data[5]之前被访问过。但是这个操作只能通过遍历to数组的方式。（这里加一个指示变量top，免得我们遍历整个to数组）
遍历to数组显然不是我们想要的方式，因为这会增加程序执行时间。有没有更直接的办法呢？
有，但是需要增加空间。通过前面的操作，我们容易看出to数组中记录的元素跟访问data[]数组中元素的顺序很相关。比如：我们先访问的data[1]，所以下标1就记录在to数组的第0号位置。最后访问的data[3]，那么下标3就记录在to数组的第2号位置。基于这个特点，我们的想法应该是记录下访问的顺序，因此加入from数组来记录访问data数组中元素的顺序。
再次分析。我们首先访问的是data[1]，因此我们在from[1]位置记录0，代表data[1]是最先访问的，并在to数组中记录下标1；我们第二个访问的是data[5]，于是我们把from[5]位置记录1，代表data[5]是第二个被访问的，相应的，to数组记录下标5，以此类推。
现在我们判断data数组中的某个元素(下标为i)是否被访问过的主要条件就是：
to[from[i]] == i
这个式子很容易理解，from[i]就代表我们访问data数组的时候是第几个访问访问到的。如果式子相等，说明data中的这个元素我们之前访问过。
但是这个式子不是很严谨，因为如果data[i]没有被访问过，那么from数组对应的from[i]应该就是随机值，以这个随机值为to数组的下标，我们也会得到一个随机值，这个随即值有很小很小的几率等于i，这就是不严谨的原因。于是我们的式子改进为：
from[i] < top & to[from[i]] == i
top 的初值为0，from[]中的所有元素都是大于等于0的。这样就保证了式子的严谨性。
最后给出每访问一个data数组中元素，这些数组或者变量的改变方式：
from[i] = top;
to[top] = i;
data[i] = 0;
top++;
