侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 675 篇文章
  • 累计创建 128 个标签
  • 累计收到 20 条评论

目 录CONTENT

文章目录

【并查集】修改数组【蓝桥杯】

GabrielxD
2023-03-31 / 0 评论 / 0 点赞 / 191 阅读 / 560 字
温馨提示:
本文最后更新于 2023-03-31,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

题目

修改数组 - 蓝桥云课


题目描述

给定一个长度为 NN 的数组 A=[A1,A2,,AN]A = [A_1,A_2,··· ,A_N] ,数组中有可能有重复出现的整数。

现在小明要按以下方法将其修改为没有重复整数的数组。小明会依次修改 A2,A3,,ANA_2,A_3,··· ,A_N

当修改 AiA_i 时,小明会检查 AiA_i 是否在 A1A_1Ai1A_i−1 中出现过。如果出现过,则小明会给 AiA_i 加上 1 ;如果新的 AiA_i 仍在之前出现过,小明会持续给 AiA_i 加 1 ,直 到 AiA_i 没有在 A1A_1Ai1A_i−1 中出现过。

ANA_N 也经过上述修改之后,显然 AA 数组中就没有重复的整数了。

现在给定初始的 AA 数组,请你计算出最终的 AA 数组。

输入描述

第一行包含一个整数 NN

第二行包含 NN 个整数 A1,A2,,ANA_1,A_2,··· ,A_N

其中, 1N1051Ai1061 \leq N \leq 10^5,1 \leq A_i \leq 10^6

输出描述

输出 NN 个整数,依次是最终的 A1,A2,,ANA_1,A_2,··· ,A_N

输入输出样例

示例

输入

5
2 1 1 3 4

输出

2 1 3 4 5

运行限制

  • 最大运行时间:1s
  • 最大运行内存: 256M

解题

方法一:单链表式的并查集

思路

image-20230331161437644

代码

import java.util.*;
import java.io.*;

public class Main {
    static final int N = (int) 1e6 + 10;
    static int[] roots = new int[N];
    static {
        for (int i = 1; i < N; ++i) roots[i] = i;
    }

    static int find(int x) {
        return roots[x] == x ? x : (roots[x] = find(roots[x]));
    }

    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        in.nextToken(); int n = (int) in.nval;
        for (int i = 0; i < n; ++i) {
            in.nextToken(); int x = (int) in.nval;
            x = find(x); 
            roots[x] = x + 1;
            System.out.print(x + " ");
        }
    }
}
0
博主关闭了所有页面的评论