修改数组题解

解题思路:

暴力模拟到并查集

注意事项:

参考代码:

暴力模拟 没有AC

N = int(input())
##inputList = [int(temp) for temp in input().strip().split()]
inputList = [10000 for i in range(10000)]
numberList = [inputList[0]]

for i in range(1,N):
    while inputList[i] in numberList:
        inputList[i] = inputList[i] + 1
    numberList.append(inputList[i])

for temp in numberList:
    if temp == numberList[-1]:
        print(temp, end="")
    else:
        print(temp, end=" ")

并查集

# 并查集 用于处理元素分组 管理一些不相交的集合 如血姻关系
def find(x):
    global fa
    if fa[x] != x:
        fa[x] = find(fa[x])
    return fa[x]

N = int(input())

A = [int(temp) for temp in input().strip().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
    # 其次为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="")
    if i != N - 1:
        print(" ", end="")