蓝桥杯-修改数组

举报
别团等shy哥发育 发表于 2023/04/04 23:11:46 2023/04/04
【摘要】 @toc 1、题目描述给定一个长度为 N 的数组 a=[A1,A2,...,AN]a=[A_1,A_2,...,A_N]a=[A1​,A2​,...,AN​],数组中有可能有重复出现的整数。现在小明要按以下方法将其修改为没有重复整数的数组。小明会依次修改A2,A3,...,ANA_2,A_3,...,A_NA2​,A3​,...,AN​当修改AiA_iAi​时,小明会检查AiA_iAi​是否...

@toc

1、题目描述

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

现在小明要按以下方法将其修改为没有重复整数的数组。小明会依次修改 A 2 , A 3 , . . . , A N A_2,A_3,...,A_N

当修改 A i A_i 时,小明会检查 A i A_i 是否在中出 A 1 A i 1 A_1\sim A_i-1 现过。如果出现过,则小明会给 A i A_i 加上 1 ;如果新的A_i仍在之前出现过,小明会持续给 加 A i A_i 1 ,直 到 A i A_i 没有在 A 1 A i 1 A_1\sim A_i-1 中出现过。

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

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

输入描述

第一行包含一个整数 N

第二行包含N个整数 A 1 , A 2 , . . . , A N A_1,A_2,...,A_N

其中,1≤N 1 0 5 10^5 ,1≤* A i A_i *≤ 1 0 6 10^6

输出描述

输出 N 个整数,依次是最终的 A 1 , A 2 , . . . , A N A_1,A_2,...,A_N

输入输出样例

示例

输入

5
2 1 1 3 4

输出

2 1 3 4 5

运行限制

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

2、解题思路

2.1 思路一:暴力法(超时)

用一个exist[]数组标记输入的x是否已经被使用过exist[x]=1,若已经被使用过,则执行x++。这个思路倒是很清晰,就是超时了。

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.ArrayList;


/**
 * 暴力:用一个数组exist标记输入的x是否被使用过(exist[x]=1),若已经被使用过,则执行x++
 */
public class Main {
    public static int[] exist=new int[1000010];
    public static StreamTokenizer st=new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    public static void main(String[] args) throws IOException {
        int n = nextInt();
        ArrayList<Integer> list = new ArrayList<>();
        for (int i = 1; i <=n ; i++) {
            int x = nextInt();
            while(exist[x]==1){
                x++;
            }
            exist[x]=1;
            list.add(x);
        }
        list.forEach(x->{
            System.out.print(x+" ");
        });
    }
    public static int nextInt() throws IOException{
        st.nextToken();
        return (int)st.nval;
    }
}

2.2 思路二:并查集(AC)

假设我们当前的输入为2 1 1 3 4,我们使用一个father[]数组保存每个节点的父节点,使用a数组保存最终每个位置上的结果。

以输入[2,1,1,3,4]为例,初始的时候,我们让每个节点都指向自己。

//并查集初始化 
for (int i = 1; i <=MAXN; i++) {
      father[i]=i;
	}

没输入一个数字,我们就去查找它的根节点,把他根节点的值当作这个位置的最终结果。

比如,

先输入2,查2的根节点为2,则最终结果:[2],然后将[2,3]合并,让2指向3,如下图:

image-20230331213222862

这样做的目的是,在下一次还输入2的时候,直接把2的根节点值3当作本次的最终结果。

再输入1,查1的根节点,1的根节点还是1,所以此时最终结果为:[2,1],然后将1和(1+1=2)执行合并,让1的根节点指向2的根节点,此时结果如下图:

image-20230331213536838

接着输入1,查找1的根节点为3,直接把3当作本次的结果,则此时最终结果为:[2,1,3],然后执行3和(3+1=4)的合并,结果如下右图

image-20230331214820637

本来应该为作图,但是由于路径压缩操作的存在,最终的结果为右图。

接着输入3,查找3的根节点为4,则此时的最终结果为:[2,1,3,4],然后执行4和(4+1=5)的合并,结果如下图:

image-20230331214904881

接着输入4,查找4的根节点为5,所以此时的最终结果:[2,1,3,4,5],然后执行5和(5+1=6)的合并就行,到这里已经结束了,就不再画出5和6的合并结果了。

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.Arrays;
/**
 * 并查集
 */
public class Final {
    public static final int MAXN=1000000;
    public static int n;
    //并查集数组,father[i]
    public static int[] father=new int[1000010];
    public static int[] a=new int[1000010];//保存结果
    public static StreamTokenizer st=new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    public static void main(String[] args) throws IOException {
        n=nextInt();
        init();
        for (int i = 1; i <=n; i++) {
            int x=nextInt();
            int root =find(x);
            a[i]=root;  //保存结果
            union(root,root+1);
        }
        Arrays.stream(a).skip(1).limit(n).forEach(x->{
            System.out.print(x+" ");
        });
    }
    //并查集初始化
    public static void init(){
        for (int i = 1; i <=MAXN; i++) {
            father[i]=i;
        }
    }
    //查找父节点:路径压缩,否则会超时
    public static int find(int x){
        if(father[x]==x){
            return x;
        }else{
            //注意在不断查找根节点的过程中要路径压缩
             father[x]=find(father[x]);
             return father[x];
        }
    }
    public static void union(int x,int y){
        int father_x = find(x); //找到x的祖先
        int father_y = find(y); //找到y的祖先
        father[father_x]=father_y;//让x的祖先指向y的祖先
    }
    public static int nextInt() throws IOException{
        st.nextToken();
        return (int)st.nval;
    }
}

image-20230331215052076

image-20230331215107412

【声明】本内容来自华为云开发者社区博主,不代表华为云及华为云开发者社区的观点和立场。转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息,否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。