Question

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

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++;
}