【leecode】1806.还原排列的最少操作步数

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/minimum-number-of-operations-to-reinitialize-a-permutation

给你一个偶数 $n$​​​​​​ ，已知存在一个长度为 n 的排列 $perm$ ，其中 $perm[i]==i$（下标 从 0 开始 计数）。

一步操作中，你将创建一个新数组 $arr$ ，对于每个 $i$ ：

如果 $i$，那么 $arr[i]=perm[i/2]$
如果 $i$ ，那么 $arr[i]=perm[n/2+(i-1)/2]$
然后将 $arr$​​ 赋值​​给 $perm$ 。

要想使 $perm$ 回到排列初始值，至少需要执行多少步操作？返回最小的 非零 操作步数。

这道题，刚拿到题目没有读懂题 ，解了好半天也没解出来，后来看了题解才发现 原来 题目中的一步操作就是对数组的操作 即每一步操作都是将数组进行赋值，求多少次数组赋值才能得到原数组
当然：此时暴力解法很简单，直接模拟操作即可，但是这样的解法显然不是题目的用意。
当每次操作时

当$i!=0且i!=n$时$perrm[i]$ 都换到了$perm[2imod(n-1)]$
则当perm[i[依旧换到原来位置时
令 $f(x)=2xmod(n-1)$
则第二次则为$f(f(x))=2(2xmod(n-1))mod(n-1)$
其中内部的mod操作可以省略则 $f(f(x))=2\ast 2xmod(n-1)$
即 $f^n(x)=2^{n}xmod(n-1)$

若想回归原位则当$x=2^{n}xmod(n-1)$即 $1=2^{n}mod(n-1)$时 回归原数组
则java代码为

class Solution {
    public int reinitializePermutation(int n) {
        int ans=0;
        int pos=1;
         do{
            if(pos%2==1)pos = (pos+n-1)/2;
            else pos = pos/2;
            ans++;
        }while(pos!=1);
        return ans;
        
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13