[蓝桥杯]修改数组
修改数组
题目描述
给定一个长度为 NN 的数组 A=[A1,A2,⋅⋅⋅,AN]A=[A1,A2,⋅⋅⋅,AN]，数组中有可能有重复出现的整数。
现在小明要按以下方法将其修改为没有重复整数的数组。小明会依次修改A2,A3,⋅⋅⋅,ANA2,A3,⋅⋅⋅,AN。
当修改 AiAi 时，小明会检查 AiAi 是否在 A1A1 ∼ Ai−1Ai−1 中出现过。如果出现过，则小明会给 AiAi 加上 1 ；如果新的 AiAi 仍在之前出现过，小明会持续给 AiAi 加 1 ，直 到 AiAi 没有在 A1A1 ∼ Ai−1Ai−1 中出现过。
当 ANAN 也经过上述修改之后，显然 AA 数组中就没有重复的整数了。
现在给定初始的 AA 数组，请你计算出最终的 AA 数组。
输入描述
第一行包含一个整数 NN。
第二行包含 NN 个整数 A1,A2,⋅⋅⋅,ANA1,A2,⋅⋅⋅,AN。
其中，1≤N≤105，1≤Ai≤1061≤N≤105，1≤Ai≤106。
输出描述
输出 NN 个整数，依次是最终的 A1,A2,⋅⋅⋅,ANA1,A2,⋅⋅⋅,AN。
输入输出样例
示例
输入
5
2 1 1 3 4
输出
2 1 3 4 5
运行限制
- 最大运行时间：1s
- 最大运行内存: 256M
总通过次数: 6130 | 总提交次数: 8905 | 通过率: 68.8%
难度: 困难 标签: 2019, 并查集, 省赛
算法思路
本题需要高效处理数组重复元素，核心挑战在于避免暴力解法的O(n²)时间复杂度。最优解法使用并查集，通过路径压缩实现高效查找：
- 并查集维护：每个数字指向下一个可用值
- 路径压缩：查询时优化后续访问路径
- 动态分配：处理数字递增时的关联关系
https://oi-wiki.org/ds/images/dsu1.png
并查集路径压缩示意图
代码实现（C++）
#include <iostream>
using namespace std;const int MAX = 2000005; // 最大数值范围
int fa[MAX]; // 并查集数组// 带路径压缩的并查集查询
int find(int x) {if (x != fa[x]) fa[x] = find(fa[x]); // 路径压缩return fa[x];
}int main() {ios::sync_with_stdio(false);cin.tie(0);int n;cin >> n;// 初始化并查集for (int i = 1; i < MAX; i++) fa[i] = i;// 处理每个数字for (int i = 0; i < n; i++) {int num;cin >> num;int root = find(num); // 找到当前可用值cout << root << " ";fa[root] = find(root + 1); // 指向下一个可用值}return 0;
}算法步骤详解
- 初始化：创建并查集数组
fa，初始每个元素指向自己 - 处理元素：
- 输入数字
num - 通过
find(num)找到实际可用值root - 输出
root并更新fa[root] = find(root+1)
- 输入数字
- 路径压缩：
find()函数递归优化查询路径
代码解析
-
并查集设计：
fa数组存储每个数字的下一个可用值- 初始状态：
fa[i] = i（每个数字都可用）
-
路径压缩：
if (x != fa[x]) fa[x] = find(fa[x]); // 核心优化将查询路径上的所有节点直接指向根节点，大幅减少后续查询时间
-
动态更新：
fa[root] = find(root + 1);当前数字使用后，指向下一个可用数字的根（处理连续被占用情况）
实例验证
输入：5\n2 1 1 3 4
处理过程：
- 初始：
fa[1]=1, fa[2]=2,... - 处理
2→find(2)=2，输出2，设置fa[2]=find(3)=3 - 处理
1→find(1)=1，输出1，设置fa[1]=find(2)=3（因fa[2]=3） - 处理
1→find(1)=find(3)=3，输出3，设置fa[3]=find(4)=4 - 处理
3→find(3)=4，输出4，设置fa[4]=find(5)=5 - 处理
4→find(4)=5，输出5
输出：2 1 3 4 5✅
注意事项
-
数组大小：
- 需设置
MAX = 初始最大值 + n + 5（示例中2000005） - 最坏情况：所有元素为1，最大值为1 + n
- 需设置
-
时间复杂度：
- 单次
find()均摊O(α(n))（反阿克曼函数） - 整体O(nα(n)) ≈ O(n)
- 单次
-
边界处理：
- 首元素不需处理
- 输入数据保证n≥1
测试点设计
| 测试类型 | 输入样例 | 预期输出 | 验证重点 |
|---|---|---|---|
| 最小规模 | 1\n5 | 5 | 单元素处理 |
| 全相同值 | 5\n1 1 1 1 1 | 1 2 3 4 5 | 连续递增处理 |
| 无重复 | 5\n5 4 3 2 1 | 5 4 3 2 1 | 无修改情况 |
| 边界值 | 100000\n(全1) | 1 2 ... 100000 | 最大数据性能 |
| 混合重复 | 6\n2 2 1 3 3 1 | 2 3 1 4 5 6 | 非连续重复 |
优化建议
-
内存优化：
vector<int> fa(MAX); // 动态分配根据n动态设置MAX值，减少内存占用
-
输入优化：
ios::sync_with_stdio(false); cin.tie(0); // 解除IO同步 -
非递归查询（避免递归爆栈）：
int find(int x) {int root = x;while (root != fa[root]) root = fa[root];while (x != root) {int next = fa[x];fa[x] = root;x = next;}return root; } -
预分配空间：
fa.reserve(MAX); // 减少vector扩容