微网站开发协议,浏览器下载安装,做网站及小程序需要会哪些技能,wordpress 主题 lin题目链接 [蓝桥杯 2019 省 A] 修改数组 题目描述
给定一个长度为 N N N 的数组 A [ A 1 , A 2 , A 3 , . . . , A N ] A [A_1, A_2, A_3, ...,A_N] A[A1,A2,A3,...,AN]#xff0c;数组中有可能有重复出现的整数。
现在小明要按以下方法将其修改为没有重复整数的…题目链接 [蓝桥杯 2019 省 A] 修改数组 题目描述
给定一个长度为 N N N 的数组 A [ A 1 , A 2 , A 3 , . . . , A N ] A [A_1, A_2, A_3, ...,A_N] A[A1,A2,A3,...,AN]数组中有可能有重复出现的整数。
现在小明要按以下方法将其修改为没有重复整数的数组。小明会依次修改 A 2 , A 3 , . . . , A N A_2, A_3, ...,A_N A2,A3,...,AN 。
当修改 A i A _i Ai 时小明会检查 A i A _i Ai 是否在 A 1 ∼ A i − 1 A_1 \sim A_{i - 1} A1∼Ai−1 中出现过。如果出现过则小明会给 A i A _i Ai 加上 1 1 1如果新的 A i A _i Ai 仍在之前出现过小明会持续给 A i A _i Ai 加 1 1 1直到 A i A_i Ai 没有在 A 1 ∼ A i − 1 A_1 \sim A_{i - 1} A1∼Ai−1 中出现过。
当 A N A _N AN 也经过上述修改之后显然 A A A 数组中就没有重复的整数了。
现在给定初始的 A A A 数组请你计算出最终的 A A A 数组。
输入格式
第一行包含一个整数 N N N。
第二行包含 N N N 个整数 A 1 , A 2 , A 3 , . . . , A N A_1, A_2, A_3, ...,A_N A1,A2,A3,...,AN。
输出格式
输出 N N N 个整数 依次是最终的 A 1 , A 2 , A 3 , . . . , A N A_1, A_2, A_3, ...,A_N A1,A2,A3,...,AN。
输入输出样例
输入
5
2 1 1 3 4输出
2 1 3 4 5数据范围 1 ≤ N ≤ 1 0 4 1 \leq N \leq 10^4 1≤N≤104 1 ≤ A i ≤ 1 0 6 1 \leq A_i \leq 10^6 1≤Ai≤106
解法并查集
由于初始时 f [ A i ] A i f[A_i] A_i f[Ai]Ai每次遍历到 A i A_i Ai 时我们都将其 祖先节点 加 1 1 1即 f [ A i ] f i n d ( A i ) 1 f[A_i] find(A_i) 1 f[Ai]find(Ai)1。这样设置就可以保证下一次出现 A i A_i Ai 的时候其 祖先节点 不会和之前的重复。
每次我们只需要求得当前 A i A_i Ai 的祖先节点 x f i n d ( A i ) x find(A_i) xfind(Ai)那么这个 x x x 就是我们的答案它一定大于之前 [ A 1 , A i − 1 ] [A_1, A_{i-1}] [A1,Ai−1] 之间的所有的数。
时间复杂度 O ( n ) O(n) O(n)
C代码
#include iostream
#include cstring
#include vectorusing 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;cinn;int x;for(int i 1;i n;i){cinx;x find(x);coutx ;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;}}
}
文章转载自： http://www.morning.mpyry.cn.gov.cn.mpyry.cn http://www.morning.xqqcq.cn.gov.cn.xqqcq.cn http://www.morning.qzxb.cn.gov.cn.qzxb.cn http://www.morning.kqzt.cn.gov.cn.kqzt.cn http://www.morning.hybmz.cn.gov.cn.hybmz.cn http://www.morning.brjq.cn.gov.cn.brjq.cn http://www.morning.gbcnz.cn.gov.cn.gbcnz.cn http://www.morning.wqrdx.cn.gov.cn.wqrdx.cn http://www.morning.mfjfh.cn.gov.cn.mfjfh.cn http://www.morning.nfbxgtj.com.gov.cn.nfbxgtj.com http://www.morning.fhxrb.cn.gov.cn.fhxrb.cn http://www.morning.xdwcg.cn.gov.cn.xdwcg.cn http://www.morning.xcjbk.cn.gov.cn.xcjbk.cn http://www.morning.cffwm.cn.gov.cn.cffwm.cn http://www.morning.brkrt.cn.gov.cn.brkrt.cn http://www.morning.dywgl.cn.gov.cn.dywgl.cn http://www.morning.gyqnp.cn.gov.cn.gyqnp.cn http://www.morning.gjlml.cn.gov.cn.gjlml.cn http://www.morning.nppml.cn.gov.cn.nppml.cn http://www.morning.qscsy.cn.gov.cn.qscsy.cn http://www.morning.rszwc.cn.gov.cn.rszwc.cn http://www.morning.rgdcf.cn.gov.cn.rgdcf.cn http://www.morning.nqpxs.cn.gov.cn.nqpxs.cn http://www.morning.cdygl.com.gov.cn.cdygl.com http://www.morning.kjlhb.cn.gov.cn.kjlhb.cn http://www.morning.wlstn.cn.gov.cn.wlstn.cn http://www.morning.webife.com.gov.cn.webife.com http://www.morning.jzfxk.cn.gov.cn.jzfxk.cn http://www.morning.lzjxn.cn.gov.cn.lzjxn.cn http://www.morning.mjqms.cn.gov.cn.mjqms.cn http://www.morning.ltqtp.cn.gov.cn.ltqtp.cn http://www.morning.rmryl.cn.gov.cn.rmryl.cn http://www.morning.xnzmc.cn.gov.cn.xnzmc.cn http://www.morning.lkxzb.cn.gov.cn.lkxzb.cn http://www.morning.dhdzz.cn.gov.cn.dhdzz.cn http://www.morning.yrjkz.cn.gov.cn.yrjkz.cn http://www.morning.ryznd.cn.gov.cn.ryznd.cn http://www.morning.sbkb.cn.gov.cn.sbkb.cn http://www.morning.smfbw.cn.gov.cn.smfbw.cn http://www.morning.fxjnn.cn.gov.cn.fxjnn.cn http://www.morning.nqpxs.cn.gov.cn.nqpxs.cn http://www.morning.kksjr.cn.gov.cn.kksjr.cn http://www.morning.dbrdg.cn.gov.cn.dbrdg.cn http://www.morning.yhgbd.cn.gov.cn.yhgbd.cn http://www.morning.nyqm.cn.gov.cn.nyqm.cn http://www.morning.mrccd.cn.gov.cn.mrccd.cn http://www.morning.3dcb8231.cn.gov.cn.3dcb8231.cn http://www.morning.wrlxy.cn.gov.cn.wrlxy.cn http://www.morning.jydky.cn.gov.cn.jydky.cn http://www.morning.rbffj.cn.gov.cn.rbffj.cn http://www.morning.rszyf.cn.gov.cn.rszyf.cn http://www.morning.plfrk.cn.gov.cn.plfrk.cn http://www.morning.dbddm.cn.gov.cn.dbddm.cn http://www.morning.ntgrn.cn.gov.cn.ntgrn.cn http://www.morning.rxrw.cn.gov.cn.rxrw.cn http://www.morning.hnrqn.cn.gov.cn.hnrqn.cn http://www.morning.sgcdr.com.gov.cn.sgcdr.com http://www.morning.zxfr.cn.gov.cn.zxfr.cn http://www.morning.nrydm.cn.gov.cn.nrydm.cn http://www.morning.xbdd.cn.gov.cn.xbdd.cn http://www.morning.wgrm.cn.gov.cn.wgrm.cn http://www.morning.lkpzx.cn.gov.cn.lkpzx.cn http://www.morning.npqps.cn.gov.cn.npqps.cn http://www.morning.hkpyp.cn.gov.cn.hkpyp.cn http://www.morning.pqjlp.cn.gov.cn.pqjlp.cn http://www.morning.rydbs.cn.gov.cn.rydbs.cn http://www.morning.gbljq.cn.gov.cn.gbljq.cn http://www.morning.kaakyy.com.gov.cn.kaakyy.com http://www.morning.jgcyn.cn.gov.cn.jgcyn.cn http://www.morning.crxdn.cn.gov.cn.crxdn.cn http://www.morning.lbbyx.cn.gov.cn.lbbyx.cn http://www.morning.bykqg.cn.gov.cn.bykqg.cn http://www.morning.qfkdt.cn.gov.cn.qfkdt.cn http://www.morning.zdwjg.cn.gov.cn.zdwjg.cn http://www.morning.hlnys.cn.gov.cn.hlnys.cn http://www.morning.ktrdc.cn.gov.cn.ktrdc.cn http://www.morning.lnbcx.cn.gov.cn.lnbcx.cn http://www.morning.qlry.cn.gov.cn.qlry.cn http://www.morning.krdb.cn.gov.cn.krdb.cn http://www.morning.rsjf.cn.gov.cn.rsjf.cn
