Redian新闻
>
求解一道数组找最大cycle长度的问题
avatar
求解一道数组找最大cycle长度的问题# JobHunting - 待字闺中
l*n
1
给个数组,打乱了,比如
索引 0 1 2 3 4
值 3 2 1 4 0
数组的值是下次跳的索引位置,这样的话数组有环,比如 0 -> 3 -> 4 -> 0 1 -> 2
-> 1, 求最长环的长度.
avatar
T*e
2
用一个bool数组表示visited or unvisited,从index0开始跳,每次跳都把node标成
visited,并且计数,如果跳回了其它visited的节点,说明是环,记录长度,如果下一
次跳回的visited的节点是自己则说明不存在环,每次重新跳的时候,都遍历bool数组
选择下一个没有visited的节点开始。
因为数字都不同的,所以不会出现多对一的情况。
如果不想用bool数组,可以用把数组中的值改成负值的方法标记,但要注意0的处理。
这样的复杂度估计是O(n^2)求大神更好解法。
刚才想了想其实起点是哪个不重要,每次重新跳的时候可以直接从下一个unvisited节
点开始,如果到头了发现还有没访问的点,就从头开始,这样或许能快些
avatar
s*n
3
不要用bool数组,用int set来存unvisted

【在 T******e 的大作中提到】
: 用一个bool数组表示visited or unvisited,从index0开始跳,每次跳都把node标成
: visited,并且计数,如果跳回了其它visited的节点,说明是环,记录长度,如果下一
: 次跳回的visited的节点是自己则说明不存在环,每次重新跳的时候,都遍历bool数组
: 选择下一个没有visited的节点开始。
: 因为数字都不同的,所以不会出现多对一的情况。
: 如果不想用bool数组,可以用把数组中的值改成负值的方法标记,但要注意0的处理。
: 这样的复杂度估计是O(n^2)求大神更好解法。
: 刚才想了想其实起点是哪个不重要,每次重新跳的时候可以直接从下一个unvisited节
: 点开始,如果到头了发现还有没访问的点,就从头开始,这样或许能快些

avatar
p*2
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))))
avatar
l*n
5
同求大神更好解法

【在 T******e 的大作中提到】
: 用一个bool数组表示visited or unvisited,从index0开始跳,每次跳都把node标成
: visited,并且计数,如果跳回了其它visited的节点,说明是环,记录长度,如果下一
: 次跳回的visited的节点是自己则说明不存在环,每次重新跳的时候,都遍历bool数组
: 选择下一个没有visited的节点开始。
: 因为数字都不同的,所以不会出现多对一的情况。
: 如果不想用bool数组,可以用把数组中的值改成负值的方法标记,但要注意0的处理。
: 这样的复杂度估计是O(n^2)求大神更好解法。
: 刚才想了想其实起点是哪个不重要,每次重新跳的时候可以直接从下一个unvisited节
: 点开始,如果到头了发现还有没访问的点,就从头开始,这样或许能快些

avatar
l*n
6
这已经是最好的解法了啊,有一点他说错了,这个不是O(n^2),已经是O(n)了,因为环
内visit一次,环外循环的时候判断visited一次,就是O(2n)。空间方面可以是O(n),
也可以是借助原数组达到O(1)。

【在 l**********n 的大作中提到】
: 同求大神更好解法
avatar
p*o
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
avatar
s*4
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是环)
不知道我有没有搞错什么地方, 请求大神意见
avatar
l*8
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是环)
: 不知道我有没有搞错什么地方, 请求大神意见

avatar
s*4
10
原来如此 谢谢!
avatar
i*n
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;
}
avatar
f*e
12
如果把这个数组看成有向图的一个表示方法,那么就是用DFS来找最大环,
每个数组元素的值都不同 是一个很强的条件,楼主没有明确说明这个条件是否给了,
没有给的话就要处理多点指向一点的问题。
avatar
l*n
13
给个数组,打乱了,比如
索引 0 1 2 3 4
值 3 2 1 4 0
数组的值是下次跳的索引位置,这样的话数组有环,比如 0 -> 3 -> 4 -> 0 1 -> 2
-> 1, 求最长环的长度.
avatar
T*e
14
用一个bool数组表示visited or unvisited,从index0开始跳,每次跳都把node标成
visited,并且计数,如果跳回了其它visited的节点,说明是环,记录长度,如果下一
次跳回的visited的节点是自己则说明不存在环,每次重新跳的时候,都遍历bool数组
选择下一个没有visited的节点开始。
因为数字都不同的,所以不会出现多对一的情况。
如果不想用bool数组,可以用把数组中的值改成负值的方法标记,但要注意0的处理。
这样的复杂度估计是O(n^2)求大神更好解法。
刚才想了想其实起点是哪个不重要,每次重新跳的时候可以直接从下一个unvisited节
点开始,如果到头了发现还有没访问的点,就从头开始,这样或许能快些
avatar
s*n
15
不要用bool数组,用int set来存unvisted

【在 T******e 的大作中提到】
: 用一个bool数组表示visited or unvisited,从index0开始跳,每次跳都把node标成
: visited,并且计数,如果跳回了其它visited的节点,说明是环,记录长度,如果下一
: 次跳回的visited的节点是自己则说明不存在环,每次重新跳的时候,都遍历bool数组
: 选择下一个没有visited的节点开始。
: 因为数字都不同的,所以不会出现多对一的情况。
: 如果不想用bool数组,可以用把数组中的值改成负值的方法标记,但要注意0的处理。
: 这样的复杂度估计是O(n^2)求大神更好解法。
: 刚才想了想其实起点是哪个不重要,每次重新跳的时候可以直接从下一个unvisited节
: 点开始,如果到头了发现还有没访问的点,就从头开始,这样或许能快些

avatar
p*2
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))))
avatar
l*n
17
同求大神更好解法

【在 T******e 的大作中提到】
: 用一个bool数组表示visited or unvisited,从index0开始跳,每次跳都把node标成
: visited,并且计数,如果跳回了其它visited的节点,说明是环,记录长度,如果下一
: 次跳回的visited的节点是自己则说明不存在环,每次重新跳的时候,都遍历bool数组
: 选择下一个没有visited的节点开始。
: 因为数字都不同的,所以不会出现多对一的情况。
: 如果不想用bool数组,可以用把数组中的值改成负值的方法标记,但要注意0的处理。
: 这样的复杂度估计是O(n^2)求大神更好解法。
: 刚才想了想其实起点是哪个不重要,每次重新跳的时候可以直接从下一个unvisited节
: 点开始,如果到头了发现还有没访问的点,就从头开始,这样或许能快些

avatar
l*n
18
这已经是最好的解法了啊,有一点他说错了,这个不是O(n^2),已经是O(n)了,因为环
内visit一次,环外循环的时候判断visited一次,就是O(2n)。空间方面可以是O(n),
也可以是借助原数组达到O(1)。

【在 l**********n 的大作中提到】
: 同求大神更好解法
avatar
p*o
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
avatar
s*4
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是环)
不知道我有没有搞错什么地方, 请求大神意见
avatar
l*8
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是环)
: 不知道我有没有搞错什么地方, 请求大神意见

avatar
s*4
22
原来如此 谢谢!
avatar
i*n
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;
}
avatar
f*e
24
如果把这个数组看成有向图的一个表示方法,那么就是用DFS来找最大环,
每个数组元素的值都不同 是一个很强的条件,楼主没有明确说明这个条件是否给了,
没有给的话就要处理多点指向一点的问题。
avatar
s*4
25
是啊 如果没有"每个数组元素的值都不同"这个条件 应该就要做n次dfs 而且每次都
reset visited array?
这样的话 复杂度就是O(n^2)
相关阅读
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章,不代表同意其说法或描述,仅为提供更多信息,也不构成任何建议。文章信息的合法性及真实性由其作者负责,与Redian.news及其运营公司无关。欢迎投稿,如发现稿件侵权,或作者不愿在本网发表文章,请版权拥有者通知本网处理。