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

2021-03-28

LeetCode

模拟

3 分钟读完 (大约 472 个字) 0次访问

leetcode 1806. 还原排列的最少操作步数

题目：1806. 还原排列的最少操作步数

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

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

如果 i % 2 == 0 ，那么 arr[i] = perm[i / 2]
如果 i % 2 == 1 ，那么 arr[i] = perm[n / 2 + (i - 1) / 2]。

然后将 arr 赋值给 perm 。

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

示例1:

输入: n = 2
输出: 1
解释: 最初，perm = [0,1]；第 1 步操作后，perm = [0,1]；所以，仅需执行 1 步操作

示例2:

输入: n = 4
输出: 2
解释: 最初，perm = [0,1,2,3]；第 1 步操作后，perm = [0,2,1,3]；第 2 步操作后，perm = [0,1,2,3]；所以，仅需执行 2 步操作

示例3:

输入: n = 6
输出: 4

提示:

2 <= n <= 1000
n 是一个偶数

方法：模拟

思路：根据题目进行模拟。

运行数据：执行用时：113 ms，内存消耗：38.2 MB

复杂度分析：

时间复杂度：O(n^2)。
空间复杂度：O(n)。

// LeetCode指定调用方法
public int reinitializePermutation(int n) {
    
    int[] perm  = new int[n];
    int[] arr  = new int[n];
    for (int i = 0; i < n; i++) {
        perm[i] = i;
    }
    String permStr = toString(perm);
    int count = 0;
    
    while (!permStr.equals(toString(arr))) {
        for (int i = 0; i < n; i++) {
            if (i % 2 == 0) {
                arr[i] = perm[i / 2];
            } else {
                arr[i] = perm[n / 2 + (i - 1) / 2];
            }
        }
        System.arraycopy(arr, 0, perm, 0, n);
        count++;

    }

    return count;
}

// 整形数组转字符串
private String toString(int[] a) {
    StringBuilder sb = new StringBuilder();
    for (int i = 0; i < a.length; i++) {
        sb.append(a[i]);
    }
    return sb.toString();
}