题目描述

给出A[i]基本值，输出从max(A[1 ~ i-1]没出现过的最小整数, A[i]。

样例

输入样例：

5
2 1 1 3 4

输出样例：

2 1 3 4 5

算法

(并查集) $O(nlog(n))$

输入一个A[i]并寻找祖先。
直接输出x的祖先;
更新祖先为x + 1。
巧妙地利用了p[x] = x + 1来占位置。

C++ 代码

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;
const int N = 1e6 + 5;
int n, p[N];
int find(int x){
    if(x != p[x]) p[x] = find(p[x]);
    return p[x];
}

int main(){
    cin >> n;
    for(int i = 1; i < N; i ++  ) p[i] = i;
    for(int i = 1; i <= n; i ++ ){
        int x;
        scanf("%d", &x);

        x = find(x);
        printf("%d ", x);

        p[x] = x + 1;

    }
    return 0;
}