跳到主要内容

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

链接:1806.还原排列的最少操作步数
难度:Medium
标签:数组、数学、模拟
简介:给你一个偶数 n​​​​​​ ,已知存在一个长度为 n 的排列 perm ,其中 perm[i] == i​(下标 从 0 开始 计数)。

题解 1 - cpp

  • 编辑时间:2023-01-09
  • 执行用时:32ms
  • 内存消耗:6.4MB
  • 编程语言:cpp
  • 解法介绍:模拟。
class Solution {
public:
int reinitializePermutation(int n) {
vector<int> list1(n), list2(n);
for (int i = 0; i < n; i++) list1[i] = i;
int ans = 1;
for (; ; ans += 1, list1 = list2) {
int f = true;
for (int i = 0; i < n; i++) {
if (i % 2 == 0) list2[i] = list1[i / 2];
else list2[i] = list1[n / 2 + (i - 1) / 2];
if (list2[i] != i) f = false;
}
if (f) break;
}
return ans;
}
};

题解 2 - rust

  • 编辑时间:2023-01-09
  • 执行用时:8ms
  • 内存消耗:2.3MB
  • 编程语言:rust
  • 解法介绍:同上。
impl Solution {
pub fn reinitialize_permutation(n: i32) -> i32 {
let n = n as usize;
let (mut l1, mut l2) = ((0..n).collect::<Vec<_>>(),vec![0;n] );
let mut ans = 1;
loop {
let mut f = true;
for i in 0..n {
if i % 2 == 0 {
l2[i] = l1[i / 2];
} else {
l2[i] = l1[n / 2 + (i - 1) / 2];
}
if l2[i] != i {
f = false;
}
}
if f {
break;
}
ans += 1;
l1 = l2.clone();
}
ans
}
}