s*****9
发帖数: 93 | 1 Given an array of integers where each element points to the index of the
next element how would you detect if there is a cycle in this array?
Glassdoor上看来的，题目有点不清楚，我猜应该是指向自己就算结束吧，或者指向空
就结束。
O(n)的解法怎么做？ |
a*******y
发帖数: 1040 | |
h********6
发帖数: 285 | 3 A[i] = j, A[j]是A[i]的下一个元素。
可以把出现过的index都hash起来，然后每次读一个A[i],去找有没有出现过。遍历完了
都没有出现过的话就没有环。 |
g*****g
发帖数: 34805 | 4 或者做那个+1, +2的linked list找环，啥时候追上了就是环。
【在 h********6 的大作中提到】
: A[i] = j, A[j]是A[i]的下一个元素。
: 可以把出现过的index都hash起来，然后每次读一个A[i],去找有没有出现过。遍历完了
: 都没有出现过的话就没有环。
|
l****c
发帖数: 782 | 5 Yes, this is what I read and forgot.
【在 g*****g 的大作中提到】
: 或者做那个+1, +2的linked list找环，啥时候追上了就是环。
|
a*******y
发帖数: 1040 | 6 这个不就是hash这个index就行了吗？
bool FindCycle(int a[], int n)
{
std::map indexmap;
map::iterator it;
for (int i = 0; i < n;i++)
{
indexmap[i] = false;
}
indexmap[0] = true;
for (int i = 0; i < n; i++)
{
if( indexmap[a[i]])
return true;
else
indexmap[a[i]] = true;
}
return false;
} |
h********6
发帖数: 285 | 7 这个题可以不用吧，有index的话就不用和linked list一样判断追没追上了
【在 g*****g 的大作中提到】
: 或者做那个+1, +2的linked list找环，啥时候追上了就是环。
|
g*****g
发帖数: 34805 | 8 这就是空间和时间的取舍了。恐怕两者都得知道。
【在 h********6 的大作中提到】
: 这个题可以不用吧，有index的话就不用和linked list一样判断追没追上了
|
h********6
发帖数: 285 | 9 恩，的确
【在 g*****g 的大作中提到】
: 这就是空间和时间的取舍了。恐怕两者都得知道。
|
s*****9
发帖数: 93 | 10 这个有问题吧？
a[0] = 2
a[1] = 2
a[2] = null
没有cycle, 但是函数返回true。
【在 a*******y 的大作中提到】
: 这个不就是hash这个index就行了吗？
: bool FindCycle(int a[], int n)
: {
: std::map indexmap;
: map::iterator it;
: for (int i = 0; i < n;i++)
: {
: indexmap[i] = false;
: }
: indexmap[0] = true;
|
|
|
p*****2
发帖数: 21240 | 11
感觉你访问每一个点的时候，把内容变成负数，这样你再次访问的时候就知道有环了。
【在 s*****9 的大作中提到】
: 这个有问题吧？
: a[0] = 2
: a[1] = 2
: a[2] = null
: 没有cycle, 但是函数返回true。
|
m******d
发帖数: 25 | 12 数组的问题是可能有子数组是循环。比如[null，2，3，null，5，4，6]。所以必须每
一个都遍历到。判断的时候也要考虑可能是子数组循环。 |
a*******y
发帖数: 1040 | 13 how do you store NULL in an int array? |
m******d
发帖数: 25 | 14 例如不存在的index: -1或者大于数组长度的值。
关键在于这个和linked list那题有小的不同。 |
f******s
发帖数: 659 | 15
如果一个元素自己指向自己,也是个环吧?比如a[2]=2,上面这个算法就查不出来了.
【在 a*******y 的大作中提到】
: 这个不就是hash这个index就行了吗？
: bool FindCycle(int a[], int n)
: {
: std::map indexmap;
: map::iterator it;
: for (int i = 0; i < n;i++)
: {
: indexmap[i] = false;
: }
: indexmap[0] = true;
|
p*****3
发帖数: 488 | 16
为什么这个不需要额外空间？
【在 g*****g 的大作中提到】
: 或者做那个+1, +2的linked list找环，啥时候追上了就是环。
|
k*******t
发帖数: 144 | 17 两个指针(slow, fast)就够啦，判断list有无loop也不需要额外空间。贴了个代码，比
较ugly, 凑合着看吧
bool hasLoop(int arr[], int len){
int slow = 0;
int fast = 0;
int cur = 0;
while(cur < len)
{
if(arr[slow] != -1)
{
slow = arr[slow];
}
else
{
++slow;
fast = slow;
cur = slow;
continue;
}
int i = 0;
while(i < 2 && arr[fast] != -1)
{
fast = arr[fast];
++i;
}
if(i < 2)
{
++fast;
slow = fast;
cur = fast;
}
else
{
if(fast == slow){
return true;
}
}
}
return false;
}
【在 p*****3 的大作中提到】
:
: 为什么这个不需要额外空间？
|
r**h
发帖数: 1288 | 18 我的想法是，用两个set
一个来记录当前路径上出现过的元素（判断当前元素是否在环上）
一个记录所有访问过的元素（防止重复判断）
O(N)空间O(N)时间
bool hasRing(int A[], int N){
unordered_set s, visited;
for(int i=0; i
if(visited.find(i) == visited.end()){
int curr = i;
while(curr>=0 && curr
if(s.find(curr) != s.end()){
return true;
}
s.insert(curr);
visited.insert(curr);
curr = A[curr];
}
s.clear();
}
}
return false;
}
其他想法我也考虑了一下
如果每个节点都用追赶法判断是否有环的话，时间复杂度变成O(N^2)
另外把访问过的节点设置成-1是不可行的
比如说下面的例子
1->2->3->4->5->END
6->7->3->4->5->END
实际上并没有环，但是第二次访问到3的时候发现节点的next是-1 |
Y********f
发帖数: 410 | 19 这个就是有向图（这里每个节点只有一条始发边）的环问题。一个visit数组，一个
visitStack数组（回溯的时候要重置），进行dfs就可以了。
【在 s*****9 的大作中提到】
: Given an array of integers where each element points to the index of the
: next element how would you detect if there is a cycle in this array?
: Glassdoor上看来的，题目有点不清楚，我猜应该是指向自己就算结束吧，或者指向空
: 就结束。
: O(n)的解法怎么做？
|
x*****0
发帖数: 452 | |
|
|
c********p
发帖数: 1969 | |
w*******z
发帖数: 160 | |
a****a
发帖数: 37 | 23 如果数组是well formed. 就是for any 0<=i
断有没有duplicated entry就行？如果没有，一定有circle. |
