题目：
【问题描述】给定一个长度为 N 的数组 A = [A1, A2, · · · AN]，数组中有可能有重复出现的整数。
现在小明要按以下方法将其修改为没有重复整数的数组。小明会依次修改A2, A3, · · · , AN。当修改
Ai 时，小明会检查 Ai 是否在 A1 ∼ Ai−1 中出现过。如果出现过，则小明会给 Ai 加上 1 ；如果新
的 Ai 仍在之前出现过，小明会持续给 Ai 加 1 ，直到 Ai 没有在 A1 ∼ Ai−1 中出现过。当 AN 也
经过上述修改之后，显然 A 数组中就没有重复的整数了。现在给定初始的 A 数组，请你计算出最终的 A 数组。
【输入格式】
第一行包含一个整数 N。
第二行包含 N 个整数 A1, A2, · · · , AN 。
【输出格式】
输出 N 个整数，依次是最终的 A1, A2, · · · , AN。
【样例输入】
5
2 1 1 3 4
【样例输出】
2 1 3 4 5
【数据规模】 1<=N<=100000; 1<=Ai<=1000000;
分析：一开始就像暴力试试，结果发现不行，后面就写了个二叉树，用了下二分查找，发现也还是不行，哈哈哈，最后想的头都快炸了，自己网上百度查了相关并查集的算法，还是没弄懂这题，这也是第一次写并查集的题目。于是就去直接搜了下网上网友写的代码，一看直呼牛逼，竟然还有这种奇妙的算法，真是令自己大开眼界，虽然不是自己写的，但是看了十几二十分钟终于看懂了这个用并查集解的题目，心里也很开心。好了不多说，先上我自己的暴力代码和二叉树实现的二分代码
暴力代码：
1 public class AlterArray { 2 3 private static int[] arr; 4 private static boolean[] isExist = new boolean[1000000]; 5 public static void main(String[] args) { 6 Scanner input = new Scanner(System.in); 7 int n = input.nextInt(); 8 arr = new int[n]; 9 for (int i = 0; i < n; i++) { 10 arr[i] = input.nextInt(); 11 } 12 13 // 第一个数默认已经存在 14 isExist[arr[0]] = true; 15 // 从第一个数开始遍历 16 for (int i = 1; i < arr.length; i++) { 17 while (isExist[arr[i]]) { 18 arr[i]++; 19 } 20 isExist[arr[i]] = true; 21 } 22 23 for (int i = 0; i < arr.length; i++) { 24 System.out.printf("%d ", arr[i]); 25 } 26 } 27 }
二分代码：
1 public class AlterArray2 { 2 private static int[] arr; 3 private static Node root; 4 public static void main(String[] args) { 5 Scanner input = new Scanner(System.in); 6 int n = input.nextInt(); 7 arr = new int[n]; 8 9 arr[0] = input.nextInt(); 10 root = new Node(arr[0], null, null); 11 for (int i = 1; i < n; i++) { 12 int a = input.nextInt(); 13 // 查找 14 while (BinarySortTreeUtil.find(root, a)) { 15 a++; 16 } 17 arr[i] = a; 18 BinarySortTreeUtil.add(root, arr[i]); 19 } 20 21 for (int i = 0; i < arr.length; i++) { 22 System.out.printf("%d ", arr[i]); 23 } 24 } 25 } 26 27 /** 28 * 二叉排序树 29 */ 30 class BinarySortTreeUtil { 31 32 public static void add(Node root, int data) { 33 if (!find(root, data)) { 34 addNode(root, data); 35 } 36 } 37 38 /** 39 * 添加元素 40 * 如果要添加的元素跟二叉树中的某一个元素相等则不添加 41 * @param root 42 * @param data 43 */ 44 private static void addNode(Node root, int data) { 45 if (data < root.data) { 46 if (root.left == null) { 47 // 如果左孩子为空，则直接赋值给左孩子 48 root.left = new Node(data, null, null); 49 } else { 50 // 左孩子 51 addNode(root.left, data); 52 } 53 } else if (data > root.data){ 54 if (root.right == null) { 55 // 如果右孩子为空，则直接赋值给右孩子 56 root.right = new Node(data, null, null); 57 } else { 58 // 右孩子 59 addNode(root.right, data); 60 } 61 } 62 } 63 64 /** 65 * 二分查找 66 * @param data 67 * @return 68 */ 69 public static boolean find(Node root, int data) { 70 if (root == null) { 71 return false; 72 } 73 if (data == root.data) { 74 return true; 75 } else if (data < root.data) { 76 return find(root.left, data); 77 } else { 78 return find(root.right, data); 79 } 80 } 81 } 82 83 class Node { 84 int data; 85 Node left; 86 Node right; 87 88 public Node(int data, Node left, Node right) { 89 this.data = data; 90 this.left = left; 91 this.right = right; 92 } 93 }
思路：网友的代码中用了一个长度为1000003的辅助数组f，f数组的作用是存储每个数应该存储的位置，这个数组一开始初始化为每个数都是存储在自己这个数本身的位置，而后会随着循环的执行，这个数组的某些内容可能会在不停的变化。例如：在某个数第一次出现之时，第一步find方法就会直接返回这个数，然后再对这个数进行下一个存放的位置进行查找（意思就是如果这个数现在已经出现了一次，后面再出现这个数的话，那么就要从该数的下一个位置去寻找它应该存放的位置），find方法的作用就是找到指定数它应该存放的位置,而此时位置对应的数字就是当前位置该存放的数。（再次声明一下：f[i] = val 代表的是i位置下次应该放的数为val）
网友的AC代码：
1 import java.util.*; 2 3 /** 4 * @Author LZP 5 * @Date 2021/3/18 17:37 6 * @Version 1.0 7 * <p> 8 * 并查集是什么 9 * <p> 10 * 并查集是一种用来管理元素分组情况的数据结构。并查集可以高效地进行如下操作。 11 * 不过需要注意并查集虽然可以进行合并操作，但是却无法进行分割操作 12 * 1、查询元素a和元素b是否属于同一组 13 * 2、合并元素a和元素b所在的组 14 */ 15 public class AlterArray3 { 16 static int[] a = new int[100010]; 17 18 /** 19 * f[i] = val 代表的是i应该放的位置是在val处 20 */ 21 static int[] f = new int[1000010]; 22 static int n; 23 24 /** 25 * 查找还没被取过的值 26 * @param x 27 * @return 28 */ 29 static int find(int x) { 30 if (f[x] != x) { 31 f[x] = find(f[x]); 32 } 33 // 如果f[x] == x ，说明x是第一次出现，就直接返回 34 return f[x]; 35 } 36 37 public static void main(String[] args) { 38 Scanner scanner = new Scanner(System.in); 39 n = scanner.nextInt(); 40 for (int i = 1; i <= n; i++) { 41 a[i] = scanner.nextInt(); 42 } 43 scanner.close(); 44 // 1.初始化，即把每个点所在的集合初始化为自身 45 for (int i = 1; i <= 1000003; i++) { 46 f[i] = i; 47 } 48 // 2.查找a[i]处应有的值，每次取完都把原位置的值设为下一位置的值 49 for (int i = 1; i <= n; i++) { 50 a[i] = find(a[i]); 51 /* 52 如果a[i]这个数下次再出现，就让它去找a[i]所在位置的下一个能放的位 53 置，如果下一个位置已经被放了，那么再去找下一个，就这样递归的找下去， 54 直到找到能放的位置 55 这里每次+1，就是印证了题目的要求，每次往后找，而不会返回来往前去找 56 */ 57 f[a[i]] = find(a[i] + 1); 58 } 59 for (int i = 1; i <= n; i++) { 60 System.out.print(a[i] + " "); 61 } 62 } 63 }