思路很简单就是实现有点烦 时间复杂度$O(n)$
$b$ : 标记没插入元素的位置
$cnt$:记录当前插入的数
$cb$: 根据$cnt$来找出当前缺少的数
$id1$ : 表示当前缺少的数 且缺少出的位置没有数
$id2$ : 表示当前缺少的数 缺少数的位置有数
发现如果没有出现过的数,随便插入空位置就可以了,但是出现过的数呢,直觉的想法是让它们向右移一格,这样就可以了,特判如果是一个的话,直接让将该元素空着的位置直接插入一个出现过的数,然后将该元素加入出现过的数中。
收尾:将空着的位置插入出现过的数。
#include <iostream>
#include <cstring>
#include <algorithm>
#include <map>
#include <vector>
using namespace std;
const int N = 2e5 + 10;
void solve()
{
int n;
cin >> n;
vector<int> a(n + 1,0),cnt(n + 1, 0),cb,b(n + 1, 0);
for(int i = 1,x;i <= n;i ++)
{
cin >> x;
a[i] = x;
if(x)cnt[x]++;
else b[i] ++ ;
}
for(int i = 1;i <= n;i ++)
if(!cnt[i]) cb.push_back(i);
vector<int> id1,id2;
for(int i = 0;i < cb.size();i ++)
if(b[cb[i]])
id1.push_back(cb[i]);
else id2.push_back(cb[i]);
if(id1.size() == 1)
{
a[id1[0]] = id2[0];
id2[0] = id1[0];
b[id1[0]]--;
}else
{
for(int i = 0;i < id1.size();i ++)
{
if(i + 1 < id1.size())a[id1[i]] = id1[i + 1],b[id1[i]] --;
else a[id1[i]] = id1[0],b[id1[i]] --;
}
}
int idx = 0;
for(int i = 1;i <= n;i ++)
{
if(!b[i]) continue;
a[i] = id2[idx++];
}
for (int i = 1; i <= n; i ++ )
cout << a[i] << " \n"[i == n];
}
int main()
{
int T;
cin >> T;
while(T--)
{
solve();
}
return 0;
}