2021年寒假每日一題，2017~2019年的省賽真題，本文內容由倪文迪（華東理工大學計算機系軟體192班）和羅勇軍老師提供，每日一題，關注藍橋杯專欄: https://blog.csdn.net/weixin_43914593/category_10721247.html

每題提供C++、Java、Python三種語言的代碼，

2019省賽A組第8題“修改陣列” ，題目鏈接：
http://oj.ecustacm.cn/problem.php?id=1459
https://www.dotcpp.com/oj/problem2301.html

1、題目描述

給定一個長度為N 的陣列A = [A1, A2,…,AN]，陣列中有可能有重復出現的整數，
現在小明要按以下方法將其修改為沒有重復整數的陣列，小明會依次修改A2, A3, …, AN，
當修改Ai 時，小明會檢查Ai 是否在A1~ Ai-1 中出現過，
如果出現過，則小明會給Ai 加上1 ；
如果新的Ai 仍在之前出現過，小明會持續給Ai 加1 ，直到Ai 沒有在A1~Ai-1中出現過，
當AN 也經過上述修改之后，顯然A陣列中就沒有重復的整數了，
現在給定初始的A 陣列，請你計算出最終的A 陣列，
輸入：第一行包含一個整數N(1<=N<=100000)
第二行包含N個整數A1,A2,…,AN(1<=Ai<=1000000)
輸出：輸出N個整數，依次是最終的A1,A2,…,AN

2、題解

2.1 暴力

?? 先嘗試暴力的方法：每讀入一個新的數，就檢查前面是否出現過，每一次需要檢查前面所有的數，共有 n n n個數，每個數檢查 O ( n ) O(n) O(n)次，所以總復雜度是 O ( n 2 ) O(n^2) O(n2)的，超時，

2.2 hash

?? 容易想到一個改進的方法：用hash，定義 v i s [ ] vis[] vis[]陣列， v i s [ i ] vis[i] vis[i]表示數字 i i i是否已經出現過，這樣就不用檢查前面所有的數了，基本上可以在 O ( 1 ) O(1) O(1)的時間內定位到，
??然而，本題有個特殊的要求：“如果新的 A i A_i Ai?仍在之前出現過，小明會持續給 A i A_i Ai?加1 ，直到 A i A_i Ai?沒有在 A 1 A_1 A1? ~ A i ? 1 A_{i-1} Ai?1?中出現過，”這導致在某些情況下，仍然需要大量的檢查，以5個9為例：A[]={9, 9, 9, 9, 9}，
?? 第一次檢查A[1]=9，設定vis[9]=1；
?? 第二次檢查A[2]=9，先查到vis[9]=1，則把A[2]加1，變為a[2]=10，設定vis[10]=1；
?? 第三次檢查A[3]=9，先查到vis[9]=1，則把A[3]加1得A[3]=10；再查到vis[10]=1，再把A[3]加1得A[3]=11，設定vis[11]=1；
?? …
?? 復雜度仍然是 O ( n 2 ) O(n^2) O(n2)的，
?? 下面給出hash代碼，

#include<bits/stdc++.h>
using namespace std;
#define N 1000002
int vis[N]={0};   //hash:  vis[i]=1表示數字i已經存在
int main(){
	int n;	scanf("%d",&n);
	for(int i=0;i<n;i++){
		int a;
		scanf("%d",&a);  //讀一個數字
		while(vis[a]==1) //若a已經出現過，則該數加1，若加1后再出現，則繼續加
			a++;
		vis[a]=1;        //標記該數字
		printf("%d ",a); //列印
	}
}

2.3 并查集

?? 上文提到，本題用Hash方法，在特殊情況下仍然需要大量的檢查，問題出在“持續給 A i A_i Ai? 加1 ，直到 A i A_i Ai?沒有在 A 1 A_1 A1? ~ A i ? 1 A_{i-1} Ai?1?中出現過”，也就是說，問題出在那些相同的數字上，當處理一個新的 A [ i ] A[i] A[i]時，需要檢查所有與它相同的數字，
?? 如果把這些相同的數字看成一個集合，就能用并查集處理，
?? 這種并查集，必須是用“路徑壓縮”優化的，才能加快檢查速度，沒有路徑壓縮的并查集，仍然超時，
?? 學習并查集和“路徑壓縮”，參考博文：https://blog.csdn.net/weixin_43914593/article/details/104108049

2.3.1 Python代碼

N=1000002
s=[]   #并查集
def find_set(x):    #有路徑壓縮優化的查詢
    if(x != s[x]):
       s[x] = find_set(s[x])     #集的根是最新的一個數
    return s[x]
 
n=int(input())
A=str(input()).split(' ')
for i in range(N):  #并查集初始化
    s.append(i)
for i in range(n):
    A[i]=int(A[i])
    root=find_set(A[i])
    A[i]=root
    s[root]=find_set(root+1)  #加1
for i in A:
    print(i,end=' ')

2.3.2 C++代碼

#include<bits/stdc++.h>
using namespace std;

const int N=1000002;
int A[N];
int s[N];  //并查集

int find_set(int x){            //用“路徑壓縮”優化的查詢
    if(x != s[x])
       s[x] = find_set(s[x]);   //路徑壓縮
    return s[x];
}

int main(){
    for(int i=1;i<N;i++)        //并查集初始化
        s[i]=i;
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&A[i]);
        int root = find_set(A[i]);    //查詢到并查集的根
        A[i] = root;
        s[root] = find_set(root+1);   //加1
    }

    for(int i=1;i<=n;i++)
        printf("%d ",A[i]);
    return 0;
}

2.3.3 Java代碼

//oj.ecustacm.c User: 20180861115
import java.io.BufferedReader;
import java.io.InputStreamReader;
 
public class Main {
    static int max = 1000005;
    static int num[] = new int[max];
    public static int find(int x) {
        if(x == num[x]) {
            return x;
        }
        return num[x] = find(num[x]);
    }
    public static void main(String[] args)  {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        try {
            int n = Integer.parseInt(in.readLine());
            int k = 0;
            String[] s = in.readLine().split(" ");
            for(int i=1;i<=1000000;i++) {
                num[i] = i;
            }
            k = Integer.parseInt(s[0]);
            k = find(k);
            num[k] = find(k+1);
            System.out.print(k);
            for(int i=1;i<n;i++) {
                k = Integer.parseInt(s[i]);
                k = find(k);
                System.out.print(" "+k);
                num[k] = find(k+1);
            }
        }catch (Exception e) {
            e.printStackTrace();
        }
    }       
}