修改数组

mengzhuo / 2023-08-02 / 原文

传送门

思路

首先想到的是用一个集合来记录出现过的数字，每次每次查询的时间复杂度为O(1)，本来以为可以直接过的，没想到只能拿到40分

n = int(input())
arr = [int(n) for n in input().split()]
# 用来记录出现过的数字
s = set()

for i in range(n):
	# 一直累加，直到没有出现过
    while arr[i] in s:
        arr[i] += 1
    s.add(arr[i])

print(' '.join(map(str, arr)))

其实问题出在让数字累加的部分，\(A_i\)只能一个一个的累加，但其实完全可以让\(A_i\)跳跃着累加

使用一个列表S求出\(A_i\)应该改为多少（其实就是并查集）

例如，对于样例

6
2 1 1 1 3 4

刚开始列表S为（第一行为下标，第二行是值）

0	1	2	3	4	5	6
0	1	2	3	4	5	6

其中的值可以看作指针，指向一个新的下标（默认指向自己），对应的并查集为

遍历第一个元素2，根据S，S[2] == 2，指向自身，直接可以输出2，然后让S[2] = 3，这样下次遇到2的时候就可以通过S找到3

以此类推，当遍历到第三个1的时候，S为

0	1	2	3	4	5	6
0	4	3	4	4	5	6

此时对应的并查集为

根据S[1] == 4，我们可以直接输出4，不需要让1累加3次

def find(num):
    # 如何指向自身，返回
    if s[num] == num:
        # 指向下一个元素
        s[num] = num + 1
        return num
    to_return = find(s[num])
    # 路径压缩
    s[num] = to_return + 1
    return to_return


n = int(input())
arr = [int(n) for n in input().split()]
s = [i for i in range(10 ** 6 + 1)]

for i in range(n):
    arr[i] = find(s[arr[i]])

print(' '.join(map(str, arr)))