算法

(利用unordered_set，先安排，最后调整)

时间复杂度

$O(n)$

C++ 代码

#include <iostream>
#include <unordered_set>

using namespace std;
const int N = 2e5 + 10;
int a[N];

int main() {
    int T;
    cin>>T;
    while(T--) {
        int n;
        cin>>n;
        unordered_set<int> uset;
        for(int i = 1; i <= n; ++i) {
            uset.insert(i);
        }

        for(int i = 1; i <= n; ++i) {
            cin>>a[i];
            if(a[i] != 0) {
                auto iter = uset.find(a[i]);
                if(iter != uset.end()) {
                    uset.erase(iter);
                }
            }
        }

        int first = -1;
        for(int i = 1; i <= n; ++i) {
            if(uset.empty()) break;
            if(a[i] == 0) {
                auto iter = uset.begin();
                if(i == *iter) {
                    ++iter;
                }
                if(iter != uset.end()) {
                    a[i] = *iter;
                    uset.erase(iter);
                    if(first == -1) {
                        first = i;
                    }
                } else {
                    iter = uset.begin();
                    a[i] = *iter;
                    swap(a[i], a[first]);
                }
            }
        }

        for(int i = 1; i <= n; ++i) {
            cout<<a[i]<<" ";
        }
        cout<<endl;
    }

    return 0;
}