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
    }
}