算法1

思路：单链表式的并查集
p[i]表示单链表的下一个节点，i是所在树的根节点，从i从左向右找第一个没有用过的点

C++ 代码

#include<iostream>

using namespace std;
const int N=110010;
int p[N];

int find(int x)//并查集的查找函数，背过
{
    if(p[x]!=x)p[x]=find(p[x]);//边查找边压缩
    return p[x];
}
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<N;i++)p[i]=i;//让并查集的数字顺序为1 2 3 4 5
    for(int i=1;i<=n;i++)
    {
        int x;
        scanf("%d",&x);//输入
        x=find(x);//x表示从1开始，第一个没有用过的数
        printf("%d ",x);
        p[x]=x+1;//如果用过了，这个数向后延续+1
    }

    return 0;
}