蓝桥杯|历届真题:修改数组

1.题目

【问题描述】
给定一个长度为N的数组$A=[A_1,A_2,\dots,A_N]$，数组中有可能有重复出现的整数。
现在小明要按以下方法将其修改为没有重复整数的数组。小明会依次修改$A_2,A_3,\dots,A_N$当修改$A_i$；时，小明会检查$A_i$是否在$A_1 \rightarrow A_{i-1}$中出现过。如果出现过，则小明会给$A_i$加上$1$；如果新的$A_i$仍在之前出现过，小明会持续给$A_i$加上1直到$A_i$没有在$A_1 \rightarrow A_{i-1}$中出现过。
当$A_n$也经过上述修改之后，显然A数组中就没有重复的整数了。
现在给定初始的A数组，请你计算出最终的A数组。

【输入格式】
第一行包含一个整数$N$。
第二行包含N个整数$A_1,A_2,\dots,A_N$

【输出格式】
输出N个整数，依次是最终的$A_1,A_2,\dots,A_N$
【样例输入】

5
2 1 1 3 4

【样例输出】

2 1 3 4 5

【评测用例规模与约定】
对于80%的评测用例，$1 \leq N \leq 10000$。

对于所有评测用例，$1 \leq N \leq 100000,1 \leq A_i \leq 1000000$。

2. 题解

2.1 思路分析

思路1：暴力求解(80分)
用一个set保存已遍历过的数字，当遍历到新的位置时，如果再set里则一直++，再将其加入回set

思路2：并查集
维护并查集并通过查操作直接找到A_i

2.2 代码实现

• 思路1：暴力求解

// 暴力求解 80分
import java.util.*;

public class Main {
   static Scanner scanner = new Scanner(System.in);

    public static void main(String[] args) {
        int N = scanner.nextInt();
        int[] arr = new int[N];

        for (int i = 0; i < N; i++) {
            arr[i] = scanner.nextInt();
        }

        Set<Integer> set = new HashSet<>();

        for (int i = 0; i < N; i++) {
            while (set.contains(arr[i])){
                arr[i]++;
            }
            set.add(arr[i]);
        }

        for (int i = 0; i < N-1; i++) {
            System.out.print(arr[i]+" ");
        }
        System.out.println(arr[N-1]);
    }
}

• 思路2：并查集

// 并查集 80分
import java.util.*;

public class Main {
   static Scanner scanner = new Scanner(System.in);
   static int[] find = new int[1000001];

   // 查操作 找到x的真正祖先
   public static int findRoot(int x){
       return x==find[x]?x:findRoot(find[x]);
   }

    public static void main(String[] args) {
        int N = scanner.nextInt();
        int[] arr = new int[N];


        // 初始化find数组(用于查找祖先)
        for (int i = 0; i < find.length; i++) {
            find[i] = i;
        }

        for (int i = 0; i < N; i++) {
            arr[i] = scanner.nextInt();
            int root = findRoot(arr[i]); //找到目标A_{i-1}
            arr[i] = root;
            find[root] = findRoot(root+1);// 并操作 用并查集维护大小关系
        }

        for (int i = 0; i < N-1; i++) {
            System.out.print(arr[i]+" ");
        }
        System.out.println(arr[N-1]);
    }
}

// 并查集+路径压缩 100分
import java.util.*;

public class Main {
   static Scanner scanner = new Scanner(System.in);
   static int[] find = new int[1000100];

   // 查操作 找到x的真正祖先 增加路径压缩降低耗时
   public static int findRoot(int x){
       if(x==find[x]){
           return x;
       }else {
           find[x] = findRoot(find[x]);
           return find[x];
       }
   }

    public static void main(String[] args) {
        int N = scanner.nextInt();
        int[] arr = new int[N];


        // 初始化find数组(用于查找祖先)
        for (int i = 0; i < find.length; i++) {
            find[i] = i;
        }

        for (int i = 0; i < N; i++) {
            arr[i] = scanner.nextInt();
            int root = findRoot(arr[i]); //找到目标A_{i-1}
            arr[i] = root;
            find[root] = findRoot(root+1);// 并操作 用并查集维护大小关系
        }

        for (int i = 0; i < N-1; i++) {
            System.out.print(arr[i]+" ");
        }
        System.out.println(arr[N-1]);
    }
}

2.3 提交结果

• 思路1：暴力求解

• 思路2：并查集

参考资料

1. http://lx.lanqiao.cn/problem.page?gpid=T2856
2. 图论——并查集(详细版)
3. 蓝桥杯 -2019年第十届真题 修改数组 暴力|并查集