问题描述
给定一个长度为 N 的数组 A = [A?, A?, · · · AN]，数组中有可能有重复出现的整数。
现在小明要按以下方法将其修改为没有重复整数的数组。小明会依次修改
A?, A?, · · · , AN。
当修改 Ai 时，小明会检查 Ai 是否在 A? ～ Ai?? 中出现过。如果出现过，则小明会给 Ai 加上 1 ；如果新的 Ai 仍在之前出现过，小明会持续给 Ai 加 1 ，直到 Ai 没有在
A? ～ Ai?? 中出现过。
当 AN 也经过上述修改之后，显然 A 数组中就没有重复的整数了。现在给定初始的 A 数组，请你计算出最终的 A 数组。
输入格式
第一行包含一个整数 N。
第二行包含 N 个整数 A?, A?, · · · , AN 。
输出格式
输出 N 个整数，依次是最终的 A?, A?, · · · , AN。
样例输入
5
2 1 1 3 4
样例输出
2 1 3 4 5
评测用例规模与约定
对于 80% 的评测用例，1 ≤ N ≤ 10000。
对于所有评测用例，1 ≤ N ≤ 100000，1 ≤ Ai ≤ 1000000。
解题思路i
80分思路：
使用flag数组标记出现过的数字，每输入一个数字Ai，判断flag[Ai]是否为1，如果为1就一直++Ai，直到flag[Ai] == 0
同样的思路，JAVA居然能AC，JAVA题解
代码：
#include<iostream>
#include<vector>
#include<string>
#include<iomanip>
#include<cmath>
#include<numeric>
#include<algorithm>
using namespace std;
typedef long long ll;
#define rep(i,s,t) for(int i = (s);i<(t);++i)
#define N 100010
#define M 1000010
int arr[N];
bool flag[M];
int main() {
int n;
cin >> n;
rep(i, 0, n) {
cin >> arr[i];
while (flag[arr[i]]) {
++arr[i];
}
flag[arr[i]] = 1;
}
rep(i, 0, n) {
cout << arr[i] << " ";
}
return 0;
}
100分思路：
开始没想到用并查集，参考文章后有了思路。
用并查集记录每个已经出现的数字的修改值，下一次出现该数字时直接用find函数查找即可。
使已经出现的数字的根结点为该数字的修改值，即pre[arr[i]] = arr[i] + 1，如果arr[i] + 1也出现过，那么arr[i] + 1的根结点就等于arr[i] + 2，依此类推。
因为Ai 最大值为1000000，如果循环给pre数组进行赋初值的话会浪费太多时间，所以直接把所有结点的根节点初始化为0 int pre[N] = {0}，如果pre[x] == 0的话就表示x即为根节点。
但是这样依然会超时，因为虽然使用了并查集记录重复数字的修改值，可find函数在进行查找时还是会一层一层查找父结点，这样就和++Ai的操作没什么区别了。
如果能让指向父结点的子节点直接指向根节点，不就能做到O（1）的时间复杂度了吗。于是想到了并查集的路径压缩优化
代码：
#include<iostream>
#include<vector>
#include<string>
#include<iomanip>
#include<cmath>
#include<numeric>
#include<algorithm>
using namespace std;
typedef long long ll;
#define rep(i,s,t) for(int i = (s);i<(t);++i)
#define N 100010
#define M 1000010
int arr[N];
bool flag[M];
int pre[N];//所有根结点初始化为0
int find_s(int x) {
while (pre[x] != 0) {
if(pre[pre[x]] != 0)
pre[x] = pre[pre[x]];//压缩路径
x = pre[x];
}
return x;
}
int main() {
int n;
cin >> n;
rep(i, 0, n) {
cin >> arr[i];
if (flag[arr[i]]) {
arr[i] = find_s(arr[i]);
}
pre[arr[i]] = arr[i] + 1;//将arr[i]的下一个数arr[i]+1作为其根结点
flag[arr[i]] = 1;
}
rep(i, 0, n) {
cout << arr[i] << " ";
}
return 0;
}
只用了93ms，c++ yyds！
上面的代码使用的是基于循环的路径压缩，虽然能有效压缩集合树的层数，但是还没有实现我们想让所有子节点都指向根结点的效果，于是使用基于递归的路径压缩，递归查找根节点，并在逐层返回根节点的过程中，修改字节点，使每个子节点都指向根结点。
#include<iostream>
#include<vector>
#include<string>
#include<iomanip>
#include<cmath>
#include<numeric>
#include<algorithm>
using namespace std;
typedef long long ll;
#define rep(i,s,t) for(int i = (s);i<(t);++i)
#define N 100010
#define M 1000010
int arr[N];
bool flag[M];
int pre[N];//所有根结点初始化为0
int find_s(int x) {
if (pre[x] == 0) {
return x;//返回根结点
}
else {
pre[x] = find_s(pre[x]);//所有子节点指向根节点
return pre[x];
}
}
int main() {
int n;
cin >> n;
rep(i, 0, n) {
cin >> arr[i];
if (flag[arr[i]]) {
arr[i] = find_s(arr[i]);
}
pre[arr[i]] = arr[i] + 1;//将arr[i]的下一个数arr[i]+1作为其根结点
flag[arr[i]] = 1;
}
rep(i, 0, n) {
cout << arr[i] << " ";
}
return 0;
}
运行时间更短了。