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

算法

模拟

• 答案不会超过 n，直接按照题目意思模拟即可

C++ 代码

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
    bool notOk(vector<int> &perm) {
        for (int i = 0; i < perm.size(); i++) {
            if (perm[i] != i) return true;
        }
        return false;
    }
    int reinitializePermutation(int n) {
        vector<int> perm(n), arr(n);
        for (int i = 0; i < n; i++) perm[i] = i;

        int cnt = 0;
        do {
            for (int i = 0; i < n; i++) {
                if (i % 2 == 0)
                    arr[i] = perm[i / 2];
                else
                    arr[i] = perm[n / 2 + (i - 1) / 2];
            }
            for (int i = 0; i < n; i++) {
                perm[i] = arr[i];
            }
            cnt++;
        } while (notOk(perm));
        return cnt;
    }
};

时间复杂度

• 构造哈希表：O(cnt * n)，其中 cnt 为答案大小，因为 cnt < n，所以时间复杂度为 O(n^2)