What is the minimum number of operations to reinitialize a permutation?

The minimum number of operations is determined by the number of steps required to return all cycles in the permutation to their original positions. This is typically calculated by finding the Least Common Multiple (LCM) of cycle lengths.

How can I solve the Minimum Number of Operations to Reinitialize a Permutation problem efficiently?

By recognizing the cycles in the permutation and calculating the LCM of their lengths, you can efficiently determine the minimum number of operations required.

What is the key concept behind this LeetCode problem?

The key concept is the cyclical nature of the permutation and how applying the operation repeatedly moves elements along these cycles.

Can this problem be solved in linear time?

Yes, the problem can be solved efficiently by simulating the transformation and calculating the LCM of cycle lengths in linear time with respect to `n`.

What would happen if `n` were odd in the Minimum Number of Operations to Reinitialize a Permutation problem?

The problem guarantees that `n` is even, so odd values for `n` are not considered in this problem. The behavior of odd `n` would involve different cycle structures that require a distinct approach.

#1806

Medium

auto_awesome数组·数学

LeetCode 题解工作台

还原排列的最少操作步数

给你一个偶数 n ，已知存在一个长度为 n 的排列 perm ，其中 perm[i] == i （下标从 0 开始计数）。一步操作中，你将创建一个新数组 arr ，对于每个 i ：如果 i % 2 == 0 ，那么 arr[i] = perm[i / 2] 如果 i % 2 …

数组数学模拟

题目描述

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

lightbulb

解题思路

方法一：找规律 + 模拟

我们观察数字的变化规律，发现：

新数组的偶数位数字依次是原数组的前半段数字；
新数组的奇数位数字依次是原数组的后半段数字。

即，如果原数组的某个数字下标 $i$ 在 [0, n >> 1) 范围内，那么这个数字的新下标就是 i << 1；否则，新下标就是 (i - (n >> 1)) << 1 | 1。

另外，每一轮操作，数字移动的路径都是一样的，只要有一个数字（数字 $0$ 和 $n-1$ 除外）回到了它原来的位置，那么整个序列就和之前的一致了。

因此，我们选择数字 $1$ ，初始时下标也是 $1$ ，每次将数字 $1$ 移动到新的位置，直到数字 $1$ 回到原来的位置，就可以得到最小的操作次数。

时间复杂度 $O(n)$ ，空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

10

11

12

class Solution:
    def reinitializePermutation(self, n: int) -> int:
        ans, i = 0, 1
        while 1:
            ans += 1
            if i < n >> 1:
                i <<= 1
            else:
                i = (i - (n >> 1)) << 1 | 1
            if i == 1:
                return ans

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Understanding how permutations cycle is crucial to solving this problem efficiently.
question_mark
Candidates should be able to identify the cyclical behavior in the array transformations.
question_mark
A strong solution will apply mathematical techniques like LCM to minimize operations.

warning

常见陷阱

外企场景

error
Failing to recognize the cyclical nature of the permutation, leading to unnecessary brute force approaches.
error
Not properly calculating the LCM of cycle lengths, which results in incorrect operation counts.
error
Overlooking edge cases where the cycles may involve multiple small loops rather than one large cycle.

swap_horiz

进阶变体

外企场景

arrow_right_alt
What if the permutation is not initialized in the identity order?
arrow_right_alt
Can we optimize the solution if `n` is much smaller or larger than typical test cases?
arrow_right_alt
How does the solution change if the permutation is in a completely shuffled order?

help

常见问题

外企场景

继续练习

#1823 找出游戏的获胜者 #2028 找出缺失的观测数据 #2221 数组的三角和