题目描述

给定一个 1∼n 的排列 f1,f2,…,fn。

已知，对于 1≤i≤n，fi≠i 始终成立。

现在，因为一些原因，数组中的部分元素丢失了。

请你将数组丢失的部分补全，要求数组在补全后仍然是一个 1∼n 的排列，并且对于 1≤i≤n， fi≠i 均成立。

输入格式

第一行包含整数 T，表示共有 T 组测试数据。

每组数据第一行包含一个整数 n。

第二行包含 n 个整数 f1,f2,…,fn。如果 fi=0，则表示 fi 已经丢失，需要补全。

输出格式

每组数据一行，输出补全后的 f 数组，整数之间空格隔开。

如果方案不唯一，则输出任意合理方案即可。

数据范围

• 1≤T≤100，
• 2≤n≤2×105，
• 0≤fi≤n，至少两个 fi 为 0。
• 同一测试点内所有 n 的和不超过 2×105。
• 数据保证有解。

输入样例：

3
5
5 0 0 2 4
7
7 0 0 1 4 0 6
7
7 4 0 3 0 5 1

输出样例：

5 3 1 2 4
7 3 2 1 4 5 6
7 4 2 3 6 5 1

C++ 代码

#include<bits/stdc++.h>

using namespace std;

const int N = 200010;

int a[N];
bool st[N];

int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        int n;
        cin>>n;
        memset(st, 0, sizeof st);
        priority_queue<int> q; //存放丢失的位置
        for(int i=1;i<=n;i++)
        {
            cin>>a[i];
            if(a[i]==0)
            {
                q.push(i);
            }
            else st[a[i]]=1;
        }

        int last=0;//记录上一次的处理位置
        for(int i=1;i<=n;i++)
        {
            if(st[i]==0)//i为丢失的数
            {
                int t=q.top();
                q.pop();
                if(t!=i)//与位置不冲突
                {
                    a[t]=i;
                    last=t;
                }
                else //冲突
                {
                    if(last==0)//如果是首次，和下一个交换
                    {
                        a[q.top()]=i;
                        q.pop();
                        q.push(t);

                    }
                    else//如果不是首次，和上一个处理的位置交换
                    {
                        a[t]=i;
                        swap(a[t],a[last]);
                    }
                }
            }
        }

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

    return 0;
}