关注我，分享高质量每日一题题解~

b站同名账号分享力扣杯历届真题视频题解，也欢迎大家提出宝贵意见！

思路：模拟

首先，根据 y 总的思路，建立从 $i$ 到 $f(i)$ 的有向边，就将该问题转化为了环图问题，但是，我图学的很不好，所以大家还是去看 y 总的视频讲解！下面分享一下我的思路。

• 首先遍历数组，找到所有未出现的值，存入数组 $b$ 中，设共有 $m$ 个未出现的值。
• 题意要保证 $i != f(i)$，由于 $i$ 是单调递增的，那我们首先让 $f(i)$ 单调递减，并一一对应到原数组中空的位置上，这样最多只会有一个位置出现 $i = f(i)$ 的情况。
• 如何解决这种情况呢？我们记录第一个和最后一个数值（ $f(1)$ 和 $f(m)$ ）插入的位置，并选择其中一个与 $f(i)$ 对调。举个例子，在 $i > 1$ 时，根据我们的对应方式，必有 $f(1) > f(i) = i > 1$，所以我们将二者对调后，结果是 $f(1)$ 对应 $i$，$f(i)$ 对应 $1$，不会出现相等的情况。与 $f(m)$ 互换同理。但由于 $f(i)$ 可能是 $f(1)$ 和 $f(m)$ 其中的一个（也即在 $1$ 或 $m$ 位置出现了冲突），所以需要记录两个位置，选择与其中一个没有冲突的位置互换。

代码（C++）

#include <bits/stdc++.h>
using namespace std;

int main() {
    int T = 1;
    cin >> T;
    while(T--) {

        int n;
        cin >> n;
        vector<int> f(n + 1);
        vector<bool> exist(n + 1, false);

        // 先找到所有 f(i)，存到数组 b 中
        for(int i = 1 ; i <= n; i++) {
            cin >> f[i];
            if(f[i] != 0) exist[f[i]] = true; 
        }
        vector<int> b;
        for(int i = 1; i <= n; i++) {
            if(!exist[i]) b.push_back(i);
        }

        // 让 f(i) 单调递减，并一一对应
        // 同时记录 f(1)和f(m)

        sort(b.begin(), b.end(), greater<int>());
        int j = 0, l, r, m = b.size();
        for(int i = 1; i <= n; i++) {
            if(f[i] == 0) {
                f[i] = b[j];
                j++;
                if(j == 1) {
                    l = i;
                } else if(j == m) {
                    r = i;
                }
            }
        }

        // f(i) 与 f(1) 或 f(m) 互换即可
        for(int i = 1; i <= n; i++) {
            if(f[i] == i) {
                if(i != l) {
                    swap(f[l], f[i]);
                } else {
                    swap(f[r], f[i]);
                }
                break;
            }
        }

        for(int i = 1; i <= n; i++) cout << f[i] << " ";

        cout << endl;
    }
    return 0;
}

时间复杂度：$O(nlgn)$