还原排列的最少操作步数

难度: Medium

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

Submission

运行时间: 30 ms

内存: 16.0 MB

class Solution:
    def reinitializePermutation(self, n: int) -> int:
            
        """
        :type n: int
        :rtype: int
        """
        # 初始位置为1的元素的索引
        index = 1
        # 用于计数执行的步数
        steps = 0
        while True:
            # 如果索引是偶数
            if index % 2 == 0:
                index = index // 2
            # 如果索引是奇数
            else:
                index = n // 2 + (index - 1) // 2
            # 步数加1
            steps += 1
            # 如果元素回到了初始位置，终止循环
            if index == 1:
                break
        return steps

Explain

此题解侧重于追踪一个特定位置上的元素在操作过程中的移动。具体来讲，题解追踪了初始时索引为1的元素，观察这个元素如何通过给定的操作回到起始位置。算法通过模拟指定的操作，即在偶数索引时将元素置于索引的一半位置，而在奇数索引时则移动到n/2加上索引减一再除以二的位置，来确定元素回到起始位置所需的最小步数。这种方法有效地利用了循环的特性，即特定元素的运动轨迹会形成一个闭环。通过不断执行操作并记录步数，直到该元素回到初始位置，从而得到结果。

时间复杂度: O(n)

空间复杂度: O(1)

class Solution:
    def reinitializePermutation(self, n: int) -> int:
        
        \"\"\"
        :type n: int
        :rtype: int
        \"\"\"
        # 初始位置为1的元素的索引
        index = 1
        # 用于计数执行的步数
        steps = 0
        while True:
            # 如果索引是偶数
            if index % 2 == 0:
                index = index // 2
            # 如果索引是奇数
            else:
                index = n // 2 + (index - 1) // 2
            # 步数加1
            steps += 1
            # 如果元素回到了初始位置，终止循环
            if index == 1:
                break
        return steps

Explore

在这个特定的问题中，追踪索引为1的元素是因为所有的元素实际上都会经历一个循环或周期性的移动模式，最终回到它们的初始位置。索引为1的元素非常关键，因为它从第二个位置开始（在数组中索引通常从0开始），这使得它的移动能够代表或反映整体排列的状态。一旦这个元素回到其初始位置，我们可以合理推断排列已经被恢复到初始状态。因此，追踪这个元素足以判断整个数组是否重置到起始排列。

在这种情况下，由于排列操作是周期性的，并且每个元素都按照一定的规则移动，只需跟踪一个元素（特别是索引为1的元素）回到其初始位置即可。这是因为排列的操作确保了如果任何一个元素回到了初始位置，其他元素也会在循环中回到它们的初始位置。因此，只需确保跟踪的元素回到起始位置，便可推断整个排列已恢复到初始状态。

在这个算法中，`n // 2 + (index - 1) // 2` 的表达式用于计算奇数索引元素的新位置。这里，`n // 2` 是偶数位置最大索引加1，表示奇数索引位置的起始点。`(index - 1) // 2` 则是当前奇数索引减去1后再除以2，这一操作是为了找到相对于奇数索引部分的正确偏移。这种计算方式保证了元素按题目要求的方式正确移动，从而保持整个排列操作的正确性和连续性。