微网站开发协议,做淘宝网站需要多少钱,平面设计公司网站建设费用,免费婚恋网站设计题目链接 [蓝桥杯 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;}}
}
