[蓝桥杯 2019 省 A] 修改数组

题目链接

[蓝桥杯 2019 省 A] 修改数组

题目描述

给定一个长度为 $N$ 的数组 $A=[A_1,A_2,A_3,...,A_N]$，数组中有可能有重复出现的整数。

现在小明要按以下方法将其修改为没有重复整数的数组。小明会依次修改 $A_2,A_3,...,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,A_3,...,A_N$。

输出格式

输出 $N$ 个整数 ，依次是最终的 $A_1,A_2,A_3,...,A_N$。

输入输出样例

输入

5
2 1 1 3 4

输出

2 1 3 4 5

数据范围

• $1\le N\le 10^4$
• $1\le A_i\le 10^6$

解法：并查集

由于初始时 $f[A_i]=A_i$，每次遍历到 $A_i$ 时，我们都将其 祖先节点 加 $1$，即 $f[A_i]=find(A_i)+1$。这样设置就可以保证下一次出现 $A_i$ 的时候，其 祖先节点 不会和之前的重复。

每次我们只需要求得当前 $A_i$ 的祖先节点 $x=find(A_i)$，那么这个 $x$ 就是我们的答案，它一定大于之前 $[A_1,A_{i-1}]$ 之间的所有的数。

时间复杂度：$O(n)$

C++代码：

#include <iostream>
#include <cstring>
#include <vector>using namespace std;const int N = 1e6 + 10;int f[N];int find(int x)
{if(x != f[x]){f[x] = find(f[x]);}return f[x];
}void solve(){for(int i = 1;i < N;i++) f[i] = i;int n;cin>>n;int x;for(int i = 1;i <= n;i++){cin>>x;x = find(x);cout<<x<<' ';f[x] = find(x) + 1;}
}int main(){int t = 1;while(t--){solve();}return 0;
}

Java代码：

import java.io.*;
import java.util.*;public class Main
{static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));static final int N = 1000_010;static int[] f = new int[N];public static int find(int x){if(x != f[x]){f[x] = find(f[x]);}return f[x];}public static void main(String[] args) throws Exception{int n = Integer.parseInt(in.readLine().trim());String[] str = in.readLine().split(" ");for(int i = 1;i < N;i++) f[i] = i;for(int i = 0;i < n;i++){int x = Integer.parseInt(str[i]);x = find(x);System.out.print(x + " ");f[x] = find(x) + 1;}}
}