本题是一道比较简单的题目，容易看出每个位置上的数字都有固定的循环节。也就是说我们不用考虑整个数组的循环周期，而只用考虑每个位置自己的循环周期。
对于每一个位置，显然循环周期不超过N，所以我们可以O(N)的时间求出一个位置的循环周期、O(N^2)求出所有N个位置的循环周期。
最后对这N个周期求最小公倍数，即是整个数组的循环周期。
BTW，以上的算法复杂度是O(N^2)的，在时限内通过本题没有问题。但是你能想办法优化到O(N)吗？
hiho一下第167周《Array Rearrangement》题目分析
8 answer(s)
首先，置换群，可以得到所有不同长度的环，这个过程时间复杂度为O(n)。 若想将本题的时间复杂度控制在O(n)，则需对求最小公倍数的部分进行优化。
对两个数A和B（A大于B），设tempA= A%B：
1. 若tempA =0时，说明A是二者的最小公倍数;
2. 否则，令tempB = B%tempA：
2.1 若tempB = 0，则A*(B/tempA)为二者的最小公倍数；
2.2 否则，A*B 为二者的最小公倍数。
例如：5和3，5%3=1，3%1=0，最小公倍数为5*（3/1）= 15；
10和4，10%4=2，4%2=0，最小公倍数为10*（4/2）=20；
7和4，7%4=3，4%3=1，最小公倍数为7*4=28。
思路： 设cl[101]是一个一维二值数组，即若存在长度为i的环，则cl[i] =1,否则cl[i]=0。最大的环长度maxL和最小的环长度minL均可在查找环的O(n)过程中获得。
long long rst=maxL;
for(int i=maxL;i>=minL;i--){
if (c[it] == 0)continue;
int temp = rst%it;
if (temp == 0) continue;
else {
if (it%temp == 0)
rst = rst*(it / temp);
else
rst = rst*it;
}
}
将一个置换拆成若干不交的环，这一过程通过搜索和vis标记，可以做到O(n); 然后对环们的长度们求最小公倍数即可。 期望效率O(NlogN) 瓶颈在求lcm上
-
- 2017-09-11
+1
-
- 2017-09-11
哦，更正一下，期望效率应该是O(n), 证明： 效率$n+\sum_i^x{min(log_2y_i,log_2lcm(1->n-1))}$ 其中n是dfs效率，合式为求多个数lcm的效率，x为环的个数，y为每个环的长度， 于是$\sum_i^x{y_i}=n$ 那么效率中的合式的大小应该远小于n， 那么算法的瓶颈应在dfs上， 于是期望效率O(n);
-
- 2017-09-11
woc！没有数学编辑。。。好吧
- 添加评论
为啥是最小公倍数？不应该是整个数组最大的数吗？