百度面试题?解决方案
百度面试题?
网上看到的
假设存在一个超大数组,数组分配出来未初始化,现在不希望对数组进行初始化,但需要在访问数组某个元素的时候知道这个位置上的数是否是第一次被访问.判断过程需要是O(1)复杂度.如果存在预处理,预处理也应该是O(1)复杂度.可以假设存在无穷大的空间.
------解决方案--------------------
编程珠玑第二版，第一章，第9题？
------解决方案--------------------
来做个简单解释吧：
原始数组为uint Array[N];
新建两个数组分别为uint From[N]; uint To[N]
初始化一个数字为uint top = 0;
访问任意一个Array成员Array[m]时都执行如下检查：
if(From[m] < top && To[From[m]] == m)
{说明已经访问过该成员}
else
{
From[m] = top;
To[top] = m;
top++;
}
版权属于《Design and Analysis of Computer Algorithms》 1974版。
网上看到的
假设存在一个超大数组,数组分配出来未初始化,现在不希望对数组进行初始化,但需要在访问数组某个元素的时候知道这个位置上的数是否是第一次被访问.判断过程需要是O(1)复杂度.如果存在预处理,预处理也应该是O(1)复杂度.可以假设存在无穷大的空间.
------解决方案--------------------
编程珠玑第二版，第一章，第9题？
------解决方案--------------------
来做个简单解释吧：
原始数组为uint Array[N];
新建两个数组分别为uint From[N]; uint To[N]
初始化一个数字为uint top = 0;
访问任意一个Array成员Array[m]时都执行如下检查：
if(From[m] < top && To[From[m]] == m)
{说明已经访问过该成员}
else
{
From[m] = top;
To[top] = m;
top++;
}
版权属于《Design and Analysis of Computer Algorithms》 1974版。