惰性初始模式LazyInitialization

惰性初始模式 Lazy Initialization

wiki百科释义

你的代码要分配一个boolean的数组&＃xff0c;分配内存所用时间复杂度是O(1)&＃xff0c;但是分配完后&＃xff0c;数组的内容是任意值。已知&＃xff0c;数组很大&＃xff0c;我们不希望用遍历的方式初始化该数组&＃xff0c;而是采用惰性初始化模式。

问题&＃xff1a;

Design a deterministic scheme by which reads and writes to an uninitialized arrayA can be made in O(1) time. You may use O(n) additional storage; reads to uninitialized entry should return 0.

解答思路&＃xff1a;

用变量t来表示当前A中已经初始化了的元素的个数。当对A中的某个元素&＃xff0c;比如第3号元素&＃xff0c;初始化时&＃xff0c;就把3填入S[t]中&＃xff0c;然后在P[t]填入t&＃xff0c;最后t&＃43;&＃43;。也就是说&＃xff0c;S是A中已经初始化过的元素的标号&＃xff0c;P中是A中元素初始化的顺序。

假如现在要读取A[4]&＃xff0c;

if P[4]>t&＃xff0c;

说明A[4]还没被初始化&＃xff1b;

else if P[4]<&＃61;t&＃xff0c;

if  S[P[4]]&＃61;&＃61;4&＃xff0c;

说明A[4]已经被初始化过&＃xff1b;

else

说明A[4]未被初始化&＃xff1b;