蓝桥杯 修改数组 python （并查集）
题目描述
给定一个长度为 N NN 的数组 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 AA 数组中就没有重复的整数了。
现在给定初始的 A AA 数组，请你计算出最终的 A AA 数组。
输入描述
第一行包含一个整数N
第二行包含 N 个整数 
其中，
输出描述
输出 N 个整数，依次是最终的 
输入输出样例
示例
输入
5 2 1 1 3 4
输出
2 1 3 4 5
运行限制
- 最大运行时间：1s
- 最大运行内存: 256M
思路
简单的思路可以利用哈希表，类似于bool数组，如果出现了，就进行了+1得到一个，如果发生矛盾了就需要遍历整个数组，在复杂的情况下，就需要n方的复杂度，对于很大的数据这就不太现实。
可以利用并查集，这样我们得到数据就只需要O(1)就解决了
首先设置一个father数组，这个数组所有的元素都指向自身，f[i]表示当你访问到 i 个数时应该把他换成什么
一开始都是f[ i ] 指向i ，也就说明都没访问过
当你访问了 i 以后，就需要进行更新，更新f[i] = f[i+1]
因为有时候有些数据是重复的，所以当我们再次访问到i的时候，i已经输出过了，这时候我们需要输出的i+1
但是这也涉及一个问题，i+1也有可能输出过了，所以说我们就输出的是f[i+1]
代码code
# https://www.lanqiao.cn/problems/185/learning/ import os import sys # 并查集 用于处理元素分组 寻找父亲 def find(x): global fa if fa[x] != x: fa[x] = find(fa[x]) return fa[x] N = int(input()) A = list(map(int,input().split())) # 首先创建数组大小的并查集序列 自循环 全部指向自己 fa = [i for i in range(1000001)] for i in range(N): # 找到A[i]元素父亲 # 如果A[i]元素没有找到 则返回A[i]的值 同时将下一次查到A[i]值指向A[i]指向下一位 # 如果A[i]找到 则继续增加 # 2 1 1 3 4 # 首先2 的父亲是2 并同时把父亲数组中A[i]位置元素修改为3，也就是再遇到2的时候，换为3 # 其次为1 1的父亲是1 同时把父亲数组中1位置元素修改为2 # 获得1 1的父亲此时为3 输出3 并将3的父亲修改为4 # 获得3 3的父亲此时为4 输出4 并将此时3的父亲修改为5 # 获得4 4的父亲此时为5 输出5 并将此时5的父亲修改为6 A[i] = find(A[i]) fa[A[i]] = find(A[i] + 1) # 更新为下一个点指向的点 for i in range(N): print(A[i], end=" ")
