class Solution {
public:
int reinitializePermutation(int n) {
}
};
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 <= 1000n 是一个偶数原站题解
javascript 解法, 执行用时: 220 ms, 内存消耗: 48 MB, 提交时间: 2023-01-09 10:14:50
/**
* @param {number} n
* @return {number}
*/
var reinitializePermutation = function(n) {
let perm = new Array(n).fill(0).map((_, i) => i);
const target = new Array(n).fill(0).map((_, i) => i);
let step = 0;
while (true) {
const arr = new Array(n).fill(0);
for (let i = 0; i < n; i++) {
if ((i & 1) !== 0) {
arr[i] = perm[Math.floor(n / 2) + Math.floor((i - 1) / 2)];
} else {
arr[i] = perm[Math.floor(i / 2)];
}
}
perm = arr;
step++;
if (perm.toString() === target.toString()) {
break;
}
}
return step;
};
golang 解法, 执行用时: 4 ms, 内存消耗: 6.6 MB, 提交时间: 2023-01-09 10:14:32
func reinitializePermutation(n int) (step int) {
target := make([]int, n)
for i := range target {
target[i] = i
}
perm := append([]int(nil), target...)
for {
step++
arr := make([]int, n)
for i := range arr {
if i%2 == 0 {
arr[i] = perm[i/2]
} else {
arr[i] = perm[n/2+i/2]
}
}
perm = arr
if equal(perm, target) {
return
}
}
}
func equal(a, b []int) bool {
for i, x := range a {
if x != b[i] {
return false
}
}
return true
}
golang 解法, 执行用时: 0 ms, 内存消耗: 1.9 MB, 提交时间: 2023-01-09 10:14:05
func reinitializePermutation(n int) int {
if n == 2 {
return 1
}
step := 1
pow2 := 2
for pow2 != 1 {
step++
pow2 = pow2 * 2 % (n - 1)
}
return step
}
java 解法, 执行用时: 0 ms, 内存消耗: 38.6 MB, 提交时间: 2022-11-27 13:13:17
class Solution {
public int reinitializePermutation(int n) {
int ans = 1, pos =1;
pos = n/2 + (pos-1)/2;
while(pos != 1){
pos = (pos%2 == 0)? pos/2 : (n/2 +(pos-1)/2);
ans++;
}
return ans;
}
}
python3 解法, 执行用时: 28 ms, 内存消耗: 14.8 MB, 提交时间: 2022-11-27 13:12:55
class Solution:
def reinitializePermutation(self, n: int) -> int:
step = 0
ind = 1
while ind != 1 or not step:
if ind % 2:
ind = (n + ind - 1) // 2
else:
ind //= 2
step += 1
return step
python3 解法, 执行用时: 36 ms, 内存消耗: 15 MB, 提交时间: 2022-11-27 13:12:39
class Solution:
def reinitializePermutation(self, n: int) -> int:
if n == 2:
return 1
k, pow2 = 1, 2
while pow2 != 1:
k += 1
pow2 = pow2 * 2 % (n - 1)
return k