本题是一道比较简单的题目。
我们只需要循环求出S[1], S[2], ... S[N]各有多少个元素即可。
对于每一个S[K]，我们可以从A[K]开始迭代得到A[A[k]], A[A[A[K]]]...，直到出现循环节(A[K]再次出现)。这时迭代次数就是S[K]的大小。
不过如果不加优化我们会重复计算很多相同的S[K]。
比如类似下面的数据会让时间复杂度达到O(N^2)。
5
2 3 4 5 1
解决的方法是去重，如果一个A[K]已经在之前的S[1]、S[2]、... S[K-1]中出现过，那么就不必再计算S[K]。
这样时间复杂度就可以优化到O(N)。
package hihocoder;
import java.util.Scanner;
public class week271 { public static void main(String[] args) {
//读取并初始化
Scanner sc = new Scanner(System.in);
int m = sc.nextInt();
int[] arr = new int[m + 1];
int[] brr = new int[m + 1];
for (int i = 1; i <= m; i++) {
arr[i] = sc.nextInt();
brr[i] = 0;//标记是否遍历过
}
// int m = 5;
// int[] arr = new int[]{0, 2, 3, 4, 5, 1};
// int[] brr = new int[]{0, 0, 0, 0, 0, 0};
// int m = 7;
// int[] arr = new int[]{0, 6, 5, 1, 4, 2, 7, 3};
// int[] brr = new int[]{0, 0, 0, 0, 0, 0, 0, 0};
int max = 0;
//开始遍历
for (int j = 1; j <= m; j++) {
int tempMax = 1;
if (brr[j] == 1) {
continue;
}
while (j != arr[j] && 1 != brr[j]) {
brr[arr[j]] = 1;
arr[j] = arr[arr[j]];
tempMax++;
}
max = max > tempMax ? max : tempMax;
// 加速结果 大于长度的一半则直接返回结果即可
if (max > (m % 2 == 0 ? m / 2 : m / 2 + 1)) {
// System.out.println(max);
break;
}
}
System.out.println(max);
}
}
个人觉得 这就是个最大长度环的问题，第一步找环并记录环的长度同时标记已经遍历过的环节点，找环的过程循环即可。（假如最大环长度大于总长度的1/2，则直接返回结果，我觉得应该可以加速）
