原题链接:修改数组
题目描述
给定一个长度为 $N$ 的数组 $A=[A_1,A_2,⋅⋅⋅A_N]$,数组中有可能有重复出现的整数。
现在小明要按以下方法将其修改为没有重复整数的数组。
小明会依次修改 $A_2,A_3,⋅⋅⋅,A_N$。
当修改 $A_i$ 时,小明会检查 $A_i$ 是否在 $A_1∼A_{i−1}$ 中出现过。
如果出现过,则小明会给 $A_i$ 加上 $1$;如果新的 $A_i$ 仍在之前出现过,小明会持续给 $A_i$ 加 $1$,直到 $A_i$ 没有在 $A_1∼A_{i−1}$ 中出现过。
当 $A_N$ 也经过上述修改之后,显然 $A$ 数组中就没有重复的整数了。
现在给定初始的 $A$ 数组,请你计算出最终的 $A$ 数组。
输入格式
第一行包含一个整数 $N$
第二行包含 $N$ 个整数 $A_1,A_2,⋅⋅⋅,A_N$。
输出格式
输出 $N$ 个整数,依次是最终的 $A_1,A_2,⋅⋅⋅,A_N$。
数据范围
$1≤N≤105,$
$1≤Ai≤106$
输入样例1:
5
2 1 1 3 4
输出样例1:
2 1 3 4 5
思路
并查集的特殊使用
该题可以利用并查集来做,含义发生了一些变化
假设 p 为并查集中利用到的数组,并查集普通含义就是 p[i] 就是节点 i 的代表元素,而且代表元素就是 i 所在树的根节点
这里 p[i] 变为了从左往右数(数列1,…,N)第一个没有被用到的数,初始是指向自己,表示自己没有被用到
所以每次就找到利用并查集的 find 的操作,找到根,也就是从左往右数第一个没有被用到的数 x
之后 p[x] = x + 1,表示该数被用过后,指向下一个数
时间复杂度
$O(N + M)$
C++ 代码
#include <iostream>
using namespace std;
const int N = 1100010;
int p[N];
int n;
int find(int x) {
if(p[x] != x) p[x] = find(p[x]);
return p[x];
}
int main()
{
scanf("%d", &n);
for(int i = 1;i < N;i ++) p[i] = i;
for(int i = 1;i <= n;i ++) {
int x;
scanf("%d", &x);
x = find(x);
printf("%d ", x);
p[x] = x + 1;
}
return 0;
}