acwing1242. 修改数组

题目

题解

暴力（超时）

#include<iostream>
using namespace std;
const int N=1e6+10;
int a[N];
bool b[N];
int n;
int main(){
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a[i];
        while(b[a[i]])a[i]++;
        b[a[i]]=true;
    }
    for(int i=0;i<n;i++)cout<<a[i]<<" ";
    return 0;
}

并查集

用并查集找到这个点的父亲节点，然后每次+1,并将这个值付给它当父亲节点。这样就不会重复出现了。

#include<iostream>
using namespace std;
const int N=1100010;
int p[N];
int n;
int find(int x){
    if(p[x]!=x)return 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;
        cin>>x;
        x=find(x);
        cout<<x<<" ";
        p[x]=x+1;
        
    }
    return 0;
}