核心：为每个位置 $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{已占用的不同值个数})$ 。

P3416.第2题-重复元素数组

1000ms

Difficulty: 5

所属公司 : 钉钉

算法与标签>并查集

题目内容

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

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

当修改 $Ai$ 时，小明会检查 $Ai$ 是否在 $A1$ ~ $Ai-1$ 中出现过。如果出现过，则小明会给 $Ai$ 加上 $1$ ;如果新的 $Ai$ 仍在之前出现过，小明会持续给 $Ai$ 加 $1$ ，直到 $Ai$ 没有在 $A1$ ~ $Ai-1$ 中出现过。

当 $AN$ 也经过上述修改之后，显然 $A$ 数组中就没有重复的整数了。

现在给定初始的 $A$ 数组，请你帮小明计算出最终的 $A$ 数组。

第一行包含一个整数 $N$ 。

第二行包含 $N$ 个整数 $A1,A2,…,AN$ 。

其中， $1≤N≤10^5,1≤Ai≤10^6$

输出 $N$ 个整数，依次是最终的 $A1,A2,...,AN$ 。

输入

5
2 1 1 3 4

输出

2 1 3 4 5

输入

预期输出（选填）