修改数组
给定一个长度为 $N$ 的数组 $A = \left[ {A_{1},A_{2}, \cdots A_{N}} \right]$,数组中有可能有重复出现的整数。
现在小明要按以下方法将其修改为没有重复整数的数组。
小明会依次修改 $A_{2},A_{3}, \cdots ,A_{N}$。
当修改 $A_{i}$ 时,小明会检查 $A_{i}$ 是否在 $A_{1} \sim A_{i−1}$ 中出现过。
如果出现过,则小明会给 $A_{i}$ 加上 $1$;如果新的 $A_{i}$ 仍在之前出现过,小明会持续给 $A_{i}$ 加 $1$,直到 $A_{i}$ 没有在 $A_{1} \sim A_{i−1}$ 中出现过。
当 $A_{N}$ 也经过上述修改之后,显然 $A$ 数组中就没有重复的整数了。
现在给定初始的 $A$ 数组,请你计算出最终的 $A$ 数组。
输入格式
第一行包含一个整数 $N$。
第二行包含 $N$ 个整数 $A_{1},A_{2}, \cdots ,A_{N}$。
输出格式
输出 $N$ 个整数,依次是最终的 $A_{1},A_{2}, \cdots ,A_{N}$。
数据范围
$1 \leq N \leq {10}^{5}$,
$1 \leq A_{i} \leq {10}^{6}$
输入样例:
5 2 1 1 3 4
输出样例:
2 1 3 4 5
解题思路
解法一:并查集
这是一个另类并查集,有点像单链表。
$fa \left[ i \right]$表示单链表中的下一个结点。$i$所在的这颗树(集合)的根节点(代表元素)是从$i$开始向右找,第一个没有被用过的数字。也就是说,在这个集合中,只有根节点这个数字是没有被用过的,其余的数字都被用过。$i$的下一个元素(即$fa \left[ i \right]$)可能不是根节点,也可能是根节点,但通过路径压缩最后一定会指向根节点。每次用了根节点后,都把根节点并到根节点所代表的数字的下一个数字。
根据样例模拟一下:
AC代码如下:
1 #include <cstdio> 2 #include <algorithm> 3 using namespace std; 4 5 const int N = 1e5 + 1e6 + 10; 6 7 int fa[N]; 8 9 int find(int x) { 10 return fa[x] == x ? fa[x] : fa[x] = find(fa[x]); 11 } 12 13 int main() { 14 int n; 15 scanf("%d", &n); 16 17 for (int i = 1; i < N; i++) { 18 fa[i] = i; 19 } 20 21 while (n--) { 22 int val; 23 scanf("%d", &val); 24 val = find(val); // 找根节点,根节点没有用过 25 fa[val] = val + 1; // 根节点已经被用过了,把根节点并到下一个数字 26 27 printf("%d ", val); 28 } 29 30 return 0; 31 }
这种并查集的更一般用法:删除区间问题,每次删除区间$\left[ {L, R} \right]$内的数,每个数都只会删一次,但可能会重复查询某个区间,问某个数是第几次删除的。
如果删除区间$\left[ {L, R} \right]$,那就将该区间中的每个数$x$的$p\left[ x \right]$设置成$R + 1$。对于某个$x$,如果$find \left( x \right) == x$,就表示该数未被删除,否则就表示该数已被删除。
解法二:平衡树
这里的平衡树是用std::set来实现的。
用平衡树来维护连续的区间,这些区间中的数都是已经使用过的。每次遍历到一个数$x$,就查看这个数是否出现在某一个区间中,如果出现在某一个区间$\left[ {L, R} \right]$中,那么这个数只能通过加$1$加到$R + 1$,把$x$变为$R + 1$,否则就是$x$。然后把变化后的$x$插入到这些区间中,因为加入了$x$后某些区间就相邻了,因此要更新区间,把相连的两个区间合并到一个区间,比如把$\left[ {L, k} \right]$和$\left[ {k+1, R} \right]$合并成$\left[ {L, R} \right]$。
如何找到$x$是否出现在某一个区间中呢?我们只需要遍历区间的右端点,找到右端点大于等于$x$的第一个区间,然后判断这区间的左端点是否小于等于$x$,如果是,那么$x$就在这个区间中,否则不再。这里还有一个细节是,我们是用std::set::lower_bound()来找这个区间,因此我们用pair来存储左右区间的端点,但first用来存储右端点,second来存储左端点。
接下来就是合并区间的操作。我们确定了$x$更新成某个数后,是直接先把$\left[ {x, x} \right]$这个区间插入平衡树的,可以发现最多会有两次区间的合并,也就是这种情况$\left[ {L, x-1} \right]$,$\left[ {x, x} \right]$,$\left[ {x+1, R} \right]$。也有可能只合并一次,或不合并。如果发现前一个区间的右端点加上$1$后等于后一个区间的左端点,那么就合并这两个区间。
AC代码如下:
1 #include <cstdio> 2 #include <set> 3 #include <algorithm> 4 using namespace std; 5 6 typedef pair<int, int> PII; 7 8 int main() { 9 int n; 10 scanf("%d", &n); 11 12 set<PII> st; 13 while (n--) { 14 int val; 15 scanf("%d", &val); 16 17 auto t = st.lower_bound({val, -1}); // 找到右端点大于等于val的第一个区间 18 if (t != st.end() && t->second <= val) val = t->first + 1; // 这个区间要存在,且区间的左端点小于val说明val在这个区间中,val变成右端点的值加1 19 20 t = st.insert({val, val}).first; // 插入[val, val]这个区间,val被用过了,同时记录这个区间的迭代器 21 if (t != st.begin()) t--; // 如果这个区间不是第一个区间,说明前面存在一个区间,这个区间也许会与[val, val]合并,因此让迭代器指向这个区间 22 23 for (int i = 0; i < 2 && t != st.end(); i++) { // 最多进行两次区间合并 24 auto j = t; // t指向当前区间 25 j++; // j指向当前区间的下一个区间 26 27 // 如果这个区间存在,且当前区间的右端点加1后等于下一个区间的左端点,则把这两个区间合并 28 if (j != st.end() && t->first + 1 == j->second) { 29 int l = t->second, r = j->first; // 记录合并后的新区间的左右端点的值 30 st.erase(t), st.erase(j); // 把原来的两个区间删除 31 t = st.insert({r, l}).first; // 插入新区间,右端点为第一关键字,左端点为第二关键字,同时获得新区间的迭代器 32 } 33 // 否则这两个区间不可以合并 34 else { 35 t++; // 当前区间变成下一个区间 36 } 37 } 38 39 printf("%d ", val); 40 } 41 42 return 0; 43 }
参考资料
AcWing 1242. 修改数组(蓝桥杯C++ AB组辅导课):https://www.acwing.com/video/799/