原题链接
思路：
1.暴力枚举，用map标记前面是否出现过一个数，大约过60%左右的数据。
2.单链表并查集。
相当于是一个链式结构。
i的根节点表示从i开始向右找，第一个没有被用过的数。
最开始每个数都指向自己，一旦出现有个数被用过的话，就让root[x]=x+1。
图示在参考博客的聚聚那。
代码：
#include<bits/stdc++.h> using namespace std; const int maxn=1e6+7; int a[maxn],root[maxn]; int Find(int x){ if(x!=root[x]) root[x]=Find(root[x]); return root[x]; } ///i所在树的根节点表示从i开始向右找 第一个没有被用过的数 int main(){ cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; for(int i=0;i<maxn;i++) root[i]=i; for(int i=1;i<=n;i++){ a[i]=Find(a[i]); cout<<a[i]<<" "; root[a[i]]=a[i]+1; } return 0; }
