arrays - 计算数组索引

Question

如果我有一个数字数组，例如 [5, 2, 3, 2, 0, 2]

我想计算我可以连续索引数组的次数，直到我们到达我们已经访问过的索引，如下所示：

A[0] = 5 
A[5] = 2
A[2] = 3
A[3] = 2 stop here because we already indexed 2.

所以我的问题是：不使用额外的数据结构来存储以前访问过的索引，有没有办法告诉我的程序何时停止索引？

score 1 · Accepted Answer

您似乎将此数组视为有向图。如果是这样，那么您真正需要的是如何检测有向图中的循环。

看：

不过，要具体回答您的问题：如果您在迷宫中四处游荡，如何判断您以前是否去过特定的路口？您可能会考虑放弃面包屑或取消线程以提醒您去过哪里。这里也是一样。您需要使用“已访问”标志来注释原始数组，或者将您访问过的索引的副本保留在您自己的数组中。

score 0 · Accepted Answer

如果您开始时将数组元素初始化为无效值，例如 -1，那么如果已经分配了数组元素，则可以停止，如下面的伪代码所示：

if (A[x] == -1)
    A[x] = y
else
    stop

2 回答 2