hiho一下第167周《Array Rearrangement》题目分析

10
0

本题是一道比较简单的题目,容易看出每个位置上的数字都有固定的循环节。也就是说我们不用考虑整个数组的循环周期,而只用考虑每个位置自己的循环周期。

对于每一个位置,显然循环周期不超过N,所以我们可以O(N)的时间求出一个位置的循环周期、O(N^2)求出所有N个位置的循环周期。

最后对这N个周期求最小公倍数,即是整个数组的循环周期。

BTW,以上的算法复杂度是O(N^2)的,在时限内通过本题没有问题。但是你能想办法优化到O(N)吗?

  • 为啥是最小公倍数?不应该是整个数组最大的数吗?

  • 添加评论
  • reply

8 answer(s)

4

将一个置换拆成若干不交的环,这一过程通过搜索和vis标记,可以做到O(n); 然后对环们的长度们求最小公倍数即可。 期望效率O(NlogN) 瓶颈在求lcm上

  • +1

  • 哦,更正一下,期望效率应该是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);

  • woc!没有数学编辑。。。好吧

  • 添加评论
  • reply
0

Permutation Graph

2

置换群,求最小公倍数

1

这个题目是不是有问题?只有1个元素时是怎么移动的?比如 input: 1 3 output:??? 有高手能解答一下吗?

  • 不会有这样的数据。第二行一定是一个1~N的排列。

  • 但是我发现,用例子3\1,2,3 前面几个十佳代码跑出来都是1,他们也没考虑这点。是这样吗?

  • 添加评论
  • reply
0

还有, input: 3 2 2 1 output:???

如果P中元素互异且最大元素为N,那么算法的复杂度是O(N),仅需一个循环周期。

0

数组跑一遍就可以了,预期O(n)。(lcm不会影响复杂度的)

for(int i=1;i<=n;i++)if(!vis[i])a=lcm(a,dfs(i));

dfs里面配套记录所有经过的地方。

do{ans++;x=f[x];vis[x]=1;}while(x!=v);

然后开心地输出就完事。

1

首先,置换群,可以得到所有不同长度的环,这个过程时间复杂度为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;
        }
    }
0

并查集

write answer 切换为英文 切换为中文


转发分享