给定一个长度为 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
输出N个整数，依次是最终的A1,A2,··· ,AN。
5 2 1 1 3 4
2 1 3 4 5
对于 80% 的评测用例，1 ≤ N ≤ 10000。
对于所有评测用例，1 ≤ N ≤ 100000，1 ≤ Ai ≤ 1000000。
#include<iostream> #include<cstring> #include<map> using namespace std; #define MAXN 10001 /* 5 2 1 1 3 4 2 1 3 4 5 */ int main() { int n; cin >> n; int A[MAXN]; int B[MAXN]; memset(B, 0, sizeof(B)); for (int i = 0; i < n; i++) { cin >> A[i]; } B[A[0]] = 1; for (int i = 1; i < n; i++) { if (B[A[i]] == 0) B[A[i]] = 1; else { while (B[A[i]]!=0) { A[i]++; } B[A[i]] = 1; } } for (int i = 0; i < n-1; i++) { cout << A[i]<<" "; } cout << A[n - 1]; return 0; }
#include<iostream> using namespace std; #define MAXN 100001 int A[MAXN], B[MAXN]; /* 5 2 1 1 3 4 2 1 3 4 5 */ int get(int x) { return B[x] == x ? x : get(B[x]); } int main() { int n; cin >> n; for (int i = 0; i < MAXN;i++) { B[i] = i; } for (int i = 0; i < n; i++) { cin >> A[i]; int res = get(A[i]); A[i] = res; B[A[i]] = get(res + 1); } for (int i = 0; i < n-1; i++) { cout << A[i]<<" "; } cout << A[n - 1]; return 0; }
原文：https://www.cnblogs.com/hikarie/p/12563639.html