Question

C++中数组初始化的问题

假设存在一个超大数组,数组分配出来未初始化,现在不希望对数组进行初始化,但需要在访问数组某个元素的时候知道这个位置上的数是否是第一次被访问.判断过程需要是O(1)复杂度.如果存在预处理,预处理也应该是O(1)复杂度.可以假设存在无穷大的空间.
这是一道面试题，不知道该怎么回答····

Answer 1

这句话是对的啊
可以看出两点：
题目重要2点
1：假设存在无穷大的空间，说明可以另外使用空间
2：复杂度O(1)。线性判断不可行。

解决方案1：
申请1个一样大的数组。
访问原数组时，先判断那个数组的位置是否为某个设定值，如果是则访问过，
反之则没访问过。
设原数组为 A[XXX],标记数组为 B[XXX]
访问 A[X ]前先判断
if( B[ X ] == 某个值 )
{
访问过
}
else
{
B[X ] = 某个值
}
此方法有漏洞，新的标记数组也没有初始化。 若进行初始化复杂度则不保持O(1)
解决方案2：
此方法是完美方法
新建两个数组分别为From[XXX]; To[XXX]
初始化一个数字为 top = 0;
访问任意一个A成员A[m]时都执行如下检查：
if(From[m] < top && To[From[m]] == m)
{说明已经访问过该成员}
else
{
From[m] = top;
To[top] = m;
top++;
}

Answer 2

让面试者吃死