思路

• 核心：为每个位置$i$找到不小于初值$A_i$的、最小的未被使用的整数。
• 数据结构：使用“下一个可用位置”并查集（路径压缩）映射，记映射$parent[x]$表示“从$x$开始的下一个候选位置”。当某个数$y$被占用后，设$parent[y]=y+1$。
• 操作：对每个$A_i$，执行带路径压缩的查找$find(A_i)$得到最小可用的$y\ge A_i$，将其放入答案并标记$parent[y]=y+1$。
• 正确性：路径压缩保证每次返回的是当前$\ge A_i$的最小未用值；按序处理并立即占用，确保最终全局唯一且每个位置增加量最小。
• 复杂度：均摊时间复杂度为$O(N\,\alpha(U))$，其中$U$为值域上界（约为$\max(A_i)+N$），空间复杂度为$O(\text{已占用的不同值个数})$。

C++

题目内容

小红被分配到一个生成不重复元素数组的任务，对于给定一个长度为$N$的数组 $A=[A1,A2,.…,AN]$，数组中有可能有重复出现的整数。

现在小红要按以下方法将其修改为没有重复整数的数组。小红会依次修改$A2,A3,…,AN$。