l**********n
发帖数: 303 | 1 给个数组，打乱了，比如
索引 0 1 2 3 4
值 3 2 1 4 0
数组的值是下次跳的索引位置，这样的话数组有环，比如 0 -> 3 -> 4 -> 0 1 -> 2
-> 1， 求最长环的长度. |
T******e
发帖数: 157 | 2 用一个bool数组表示visited or unvisited，从index0开始跳，每次跳都把node标成
visited，并且计数，如果跳回了其它visited的节点，说明是环，记录长度，如果下一
次跳回的visited的节点是自己则说明不存在环，每次重新跳的时候，都遍历bool数组
选择下一个没有visited的节点开始。
因为数字都不同的，所以不会出现多对一的情况。
如果不想用bool数组，可以用把数组中的值改成负值的方法标记，但要注意0的处理。
这样的复杂度估计是O（n^2）求大神更好解法。
刚才想了想其实起点是哪个不重要，每次重新跳的时候可以直接从下一个unvisited节
点开始，如果到头了发现还有没访问的点，就从头开始，这样或许能快些 |
s*****n
发帖数: 994 | 3 不要用bool数组，用int set来存unvisted
【在 T******e 的大作中提到】
: 用一个bool数组表示visited or unvisited，从index0开始跳，每次跳都把node标成
: visited，并且计数，如果跳回了其它visited的节点，说明是环，记录长度，如果下一
: 次跳回的visited的节点是自己则说明不存在环，每次重新跳的时候，都遍历bool数组
: 选择下一个没有visited的节点开始。
: 因为数字都不同的，所以不会出现多对一的情况。
: 如果不想用bool数组，可以用把数组中的值改成负值的方法标记，但要注意0的处理。
: 这样的复杂度估计是O（n^2）求大神更好解法。
: 刚才想了想其实起点是哪个不重要，每次重新跳的时候可以直接从下一个unvisited节
: 点开始，如果到头了发现还有没访问的点，就从头开始，这样或许能快些
|
p*****2
发帖数: 21240 | 4 (defn f [vec]
(defn- dfs [vec start p len]
(let [next (nth vec p)]
(if (= next start)
(inc len)
(dfs vec start next (inc len)))))
(apply max (for [i (range 0 (count vec))]
(dfs vec i i 0)))) |
l**********n
发帖数: 303 | 5 同求大神更好解法
【在 T******e 的大作中提到】
: 用一个bool数组表示visited or unvisited，从index0开始跳，每次跳都把node标成
: visited，并且计数，如果跳回了其它visited的节点，说明是环，记录长度，如果下一
: 次跳回的visited的节点是自己则说明不存在环，每次重新跳的时候，都遍历bool数组
: 选择下一个没有visited的节点开始。
: 因为数字都不同的，所以不会出现多对一的情况。
: 如果不想用bool数组，可以用把数组中的值改成负值的方法标记，但要注意0的处理。
: 这样的复杂度估计是O（n^2）求大神更好解法。
: 刚才想了想其实起点是哪个不重要，每次重新跳的时候可以直接从下一个unvisited节
: 点开始，如果到头了发现还有没访问的点，就从头开始，这样或许能快些
|
l*n
发帖数: 529 | 6 这已经是最好的解法了啊，有一点他说错了，这个不是O(n^2)，已经是O(n)了，因为环
内visit一次，环外循环的时候判断visited一次，就是O(2n)。空间方面可以是O(n)，
也可以是借助原数组达到O(1)。
【在 l**********n 的大作中提到】
: 同求大神更好解法
|
p****o
发帖数: 46 | 7 why not bool array? because the size is unknown?
c++ solution:
#include
#include
using namespace std;
int findCycle(int idx[], int size){
deque visited(size, false);
int max = 1;
for (int i = 0; i < size; ++i) {
if (!visited[i]) {
visited[i] = true;
int cnt = 1;
for (int j = idx[i]; j!=i; j = idx[j]) {
visited[j] = true;
cnt++;
}
if (cnt > max) max = cnt;
}
}
return max;
}
int main(){
int idx [] = {3, 2, 1, 4, 0};
cout << findCycle (idx, 5) << endl;
}
【在 s*****n 的大作中提到】
: 不要用bool数组，用int set来存unvisted
|
s*****4
发帖数: 25 | 8 想请问一下, TeaTable提出的算法, 在这样的case能得出正确解答吗?
idx: 0 1 2 3 4
val: 2 2 4 2 2
如果我没弄错的话, 这个方法会这样做:
1. 从idx 0开始, 依次检视0 2 4 2, 发现没有环, 并把0 2 4都记为visited
2. 从idx 1开始, 依次检视1 2, 发现没有环, 并把1记为visited
3. 从idx 3开始, 依次检视3 2, 发现没有环, 并把3记为visited
4. 最终并未发现环 (但其实2 4 2是环)
不知道我有没有搞错什么地方, 请求大神意见 |
l*********8
发帖数: 4642 | 9 原题的val是0到n的一个permutation, 不会有重复值出现。
【在 s*****4 的大作中提到】
: 想请问一下, TeaTable提出的算法, 在这样的case能得出正确解答吗?
: idx: 0 1 2 3 4
: val: 2 2 4 2 2
: 如果我没弄错的话, 这个方法会这样做:
: 1. 从idx 0开始, 依次检视0 2 4 2, 发现没有环, 并把0 2 4都记为visited
: 2. 从idx 1开始, 依次检视1 2, 发现没有环, 并把1记为visited
: 3. 从idx 3开始, 依次检视3 2, 发现没有环, 并把3记为visited
: 4. 最终并未发现环 (但其实2 4 2是环)
: 不知道我有没有搞错什么地方, 请求大神意见
|
s*****4
发帖数: 25 | |
|
|
i*********n
发帖数: 58 | 11 贴个in-place的解吧：
int find_cycle(vector& A) {
int max = 0;
for(int i = 0; i < A.size(); ++ i) {
if (A[i] != i) {
int len = 0;
while(A[i] != i) {
int temp = A[i];
A[i] = A[temp];
A[temp] = temp;
len ++;
}
max = std::max(max, len);
}
}
return max;
} |
f****e
发帖数: 222 | 12 如果把这个数组看成有向图的一个表示方法，那么就是用DFS来找最大环，
每个数组元素的值都不同 是一个很强的条件，楼主没有明确说明这个条件是否给了，
没有给的话就要处理多点指向一点的问题。 |
l**********n
发帖数: 303 | 13 给个数组，打乱了，比如
索引 0 1 2 3 4
值 3 2 1 4 0
数组的值是下次跳的索引位置，这样的话数组有环，比如 0 -> 3 -> 4 -> 0 1 -> 2
-> 1， 求最长环的长度. |
T******e
发帖数: 157 | 14 用一个bool数组表示visited or unvisited，从index0开始跳，每次跳都把node标成
visited，并且计数，如果跳回了其它visited的节点，说明是环，记录长度，如果下一
次跳回的visited的节点是自己则说明不存在环，每次重新跳的时候，都遍历bool数组
选择下一个没有visited的节点开始。
因为数字都不同的，所以不会出现多对一的情况。
如果不想用bool数组，可以用把数组中的值改成负值的方法标记，但要注意0的处理。
这样的复杂度估计是O（n^2）求大神更好解法。
刚才想了想其实起点是哪个不重要，每次重新跳的时候可以直接从下一个unvisited节
点开始，如果到头了发现还有没访问的点，就从头开始，这样或许能快些 |
s*****n
发帖数: 994 | 15 不要用bool数组，用int set来存unvisted
【在 T******e 的大作中提到】
: 用一个bool数组表示visited or unvisited，从index0开始跳，每次跳都把node标成
: visited，并且计数，如果跳回了其它visited的节点，说明是环，记录长度，如果下一
: 次跳回的visited的节点是自己则说明不存在环，每次重新跳的时候，都遍历bool数组
: 选择下一个没有visited的节点开始。
: 因为数字都不同的，所以不会出现多对一的情况。
: 如果不想用bool数组，可以用把数组中的值改成负值的方法标记，但要注意0的处理。
: 这样的复杂度估计是O（n^2）求大神更好解法。
: 刚才想了想其实起点是哪个不重要，每次重新跳的时候可以直接从下一个unvisited节
: 点开始，如果到头了发现还有没访问的点，就从头开始，这样或许能快些
|
p*****2
发帖数: 21240 | 16 (defn f [vec]
(defn- dfs [vec start p len]
(let [next (nth vec p)]
(if (= next start)
(inc len)
(dfs vec start next (inc len)))))
(apply max (for [i (range 0 (count vec))]
(dfs vec i i 0)))) |
l**********n
发帖数: 303 | 17 同求大神更好解法
【在 T******e 的大作中提到】
: 用一个bool数组表示visited or unvisited，从index0开始跳，每次跳都把node标成
: visited，并且计数，如果跳回了其它visited的节点，说明是环，记录长度，如果下一
: 次跳回的visited的节点是自己则说明不存在环，每次重新跳的时候，都遍历bool数组
: 选择下一个没有visited的节点开始。
: 因为数字都不同的，所以不会出现多对一的情况。
: 如果不想用bool数组，可以用把数组中的值改成负值的方法标记，但要注意0的处理。
: 这样的复杂度估计是O（n^2）求大神更好解法。
: 刚才想了想其实起点是哪个不重要，每次重新跳的时候可以直接从下一个unvisited节
: 点开始，如果到头了发现还有没访问的点，就从头开始，这样或许能快些
|
l*n
发帖数: 529 | 18 这已经是最好的解法了啊，有一点他说错了，这个不是O(n^2)，已经是O(n)了，因为环
内visit一次，环外循环的时候判断visited一次，就是O(2n)。空间方面可以是O(n)，
也可以是借助原数组达到O(1)。
【在 l**********n 的大作中提到】
: 同求大神更好解法
|
p****o
发帖数: 46 | 19 why not bool array? because the size is unknown?
c++ solution:
#include
#include
using namespace std;
int findCycle(int idx[], int size){
deque visited(size, false);
int max = 1;
for (int i = 0; i < size; ++i) {
if (!visited[i]) {
visited[i] = true;
int cnt = 1;
for (int j = idx[i]; j!=i; j = idx[j]) {
visited[j] = true;
cnt++;
}
if (cnt > max) max = cnt;
}
}
return max;
}
int main(){
int idx [] = {3, 2, 1, 4, 0};
cout << findCycle (idx, 5) << endl;
}
【在 s*****n 的大作中提到】
: 不要用bool数组，用int set来存unvisted
|
s*****4
发帖数: 25 | 20 想请问一下, TeaTable提出的算法, 在这样的case能得出正确解答吗?
idx: 0 1 2 3 4
val: 2 2 4 2 2
如果我没弄错的话, 这个方法会这样做:
1. 从idx 0开始, 依次检视0 2 4 2, 发现没有环, 并把0 2 4都记为visited
2. 从idx 1开始, 依次检视1 2, 发现没有环, 并把1记为visited
3. 从idx 3开始, 依次检视3 2, 发现没有环, 并把3记为visited
4. 最终并未发现环 (但其实2 4 2是环)
不知道我有没有搞错什么地方, 请求大神意见 |
|
|
l*********8
发帖数: 4642 | 21 原题的val是0到n的一个permutation, 不会有重复值出现。
【在 s*****4 的大作中提到】
: 想请问一下, TeaTable提出的算法, 在这样的case能得出正确解答吗?
: idx: 0 1 2 3 4
: val: 2 2 4 2 2
: 如果我没弄错的话, 这个方法会这样做:
: 1. 从idx 0开始, 依次检视0 2 4 2, 发现没有环, 并把0 2 4都记为visited
: 2. 从idx 1开始, 依次检视1 2, 发现没有环, 并把1记为visited
: 3. 从idx 3开始, 依次检视3 2, 发现没有环, 并把3记为visited
: 4. 最终并未发现环 (但其实2 4 2是环)
: 不知道我有没有搞错什么地方, 请求大神意见
|
s*****4
发帖数: 25 | |
i*********n
发帖数: 58 | 23 贴个in-place的解吧：
int find_cycle(vector& A) {
int max = 0;
for(int i = 0; i < A.size(); ++ i) {
if (A[i] != i) {
int len = 0;
while(A[i] != i) {
int temp = A[i];
A[i] = A[temp];
A[temp] = temp;
len ++;
}
max = std::max(max, len);
}
}
return max;
} |
f****e
发帖数: 222 | 24 如果把这个数组看成有向图的一个表示方法，那么就是用DFS来找最大环，
每个数组元素的值都不同 是一个很强的条件，楼主没有明确说明这个条件是否给了，
没有给的话就要处理多点指向一点的问题。 |
s*****4
发帖数: 25 | 25 是啊 如果没有"每个数组元素的值都不同"这个条件 应该就要做n次dfs 而且每次都
reset visited array?
这样的话 复杂度就是O(n^2) |
