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

1、题干

给你一个偶数 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​​​​​​ 是一个偶数

2、思路1

根据题意模拟

3、代码

function reinitializePermutation(n: number): number {
    let perm = new Array(n).fill(0).map((v, i) => i);

    for (let ans = 1; ans; ans++) {
        let valid = true, arr = new Array(n).fill(0);

        for (let i = 0; i < n; i++) {
            if (i % 2 === 0) arr[i] = perm[i / 2];
            else arr[i] = perm[n / 2 + (i - 1) / 2];

            if (arr[i] !== i) valid = false;
        }
        
        perm = arr;
        if (valid) return ans;
    }

    return -1;
};

4、复杂度

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

5、执行结果

6、思路2

数据量不大，不打表可惜了

7、代码

function reinitializePermutation(n: number): number {
    const nums = [1, 2, 4, 3, 6, 10, 12, 4, 8, 18, 6, 11, 20, 18, 28, 5, 10, 12, 36, 12, 20, 14, 12, 23, 21, 8, 52, 20, 18, 58, 60, 6, 12, 66, 22, 35, 9, 20, 30, 39, 54, 82, 8, 28, 11, 12, 10, 36, 48, 30, 100, 51, 12, 106, 36, 36, 28, 44, 12, 24, 110, 20, 100, 7, 14, 130, 18, 36, 68, 138, 46, 60, 28, 42, 148, 15, 24, 20, 52, 52, 33, 162, 20, 83, 156, 18, 172, 60, 58, 178, 180, 60, 36, 40, 18, 95, 96, 12, 196, 99, 66, 84, 20, 66, 90, 210, 70, 28, 15, 18, 24, 37, 60, 226, 76, 30, 29, 92, 78, 119, 24, 162, 84, 36, 82, 50, 110, 8, 16, 36, 84, 131, 52, 22, 268, 135, 12, 20, 92, 30, 70, 94, 36, 60, 136, 48, 292, 116, 90, 132, 42, 100, 60, 102, 102, 155, 156, 12, 316, 140, 106, 72, 60, 36, 69, 30, 36, 132, 21, 28, 10, 147, 44, 346, 348, 36, 88, 140, 24, 179, 342, 110, 36, 183, 60, 156, 372, 100, 84, 378, 14, 191, 60, 42, 388, 88, 130, 156, 44, 18, 200, 60, 108, 180, 204, 68, 174, 164, 138, 418, 420, 138, 40, 60, 60, 43, 72, 28, 198, 73, 42, 442, 44, 148, 224, 20, 30, 12, 76, 72, 460, 231, 20, 466, 66, 52, 70, 180, 156, 239, 36, 66, 48, 243, 162, 490, 56, 60, 105, 166, 166, 251, 100, 156, 508, 9, 18, 204, 230, 172, 260, 522, 60, 40, 253, 174, 60, 212, 178, 210, 540, 180, 36, 546, 60, 252, 39, 36, 556, 84, 40, 562, 28, 54, 284, 114, 190, 220, 144, 96, 246, 260, 12, 586, 90, 196, 148, 24, 198, 299, 25, 66, 220, 303, 84, 276, 612, 20, 154, 618, 198, 33, 500, 90, 72, 45, 210, 28, 84, 210, 64, 214, 28, 323, 290, 30, 652, 260, 18, 658, 660, 24, 36, 308, 74, 60, 48, 180, 676, 48, 226, 22, 68, 76, 156, 230, 30, 276, 40, 58, 700, 36, 92, 300, 708, 78, 55, 60, 238, 359, 51, 24, 140, 121, 486, 56, 244, 84, 330, 246, 36, 371, 148, 246, 318, 375, 50, 60, 756, 110, 380, 36, 24, 348, 384, 16, 772, 20, 36, 180, 70, 252, 52, 786, 262, 84, 60, 52, 796, 184, 66, 90, 132, 268, 404, 270, 270, 324, 126, 12, 820, 411, 20, 826, 828, 92, 168, 332, 90, 419, 812, 70, 156, 330, 94, 396, 852, 36, 428, 858, 60, 431, 172, 136, 390, 132, 48, 300, 876, 292, 55, 882, 116, 443, 21, 270, 414, 356, 132, 140, 104, 42, 180, 906, 300, 91, 410, 60, 390, 153, 102, 420, 180, 102, 464, 126, 310, 40, 117, 156, 940, 220, 36, 946, 36, 316, 68, 380, 140, 204, 155, 318, 96, 483, 72, 194, 138, 60, 488, 110, 36, 491, 196, 138, 154, 495, 30, 396, 332, 36];
    return nums[n / 2 - 1];
}

8、复杂度

• 时间复杂度：$O(1)$
• 空间复杂度：$O(n)$

9、执行结果

10、思路3

基于 n 是偶数的前提可以尝试寻找操作规律。每次操作都是按固定规则分别整体移动偶数下标和奇数下标的数字，假设一次操作为一个周期，可以猜测，复原时所有数字经过的操作周期相同，因此可以只考察数字 1 复原所需的步数。（仅猜测，不会证明）

实际编码则是根据题中所给操作规则 arr[i] = perm[i / 2]、arr[i] = perm[n / 2 + (i - 1) / 2] 推断数字 1 的变化。假设 j 为数字 1 当前所处位置，则 j 下一次所处位置存在以下2种情况：

• 当 2 * j < n - 1 时 j = 2 * j
• 当 2 * j >= n - 1 时 j = 2 * j - n + 1

11、代码

function reinitializePermutation(n: number): number {
    let ans = 0;

    for (let j = 1; !(ans && j === 1); ans++) {
        if (2 * j >= n - 1) j = 2 * j - n + 1;
        else j = 2 * j;
    }

    return ans;
}

12、复杂度

• 时间复杂度：$O(n)$
• 空间复杂度：$O(1)$

13、执行结果