19年蓝桥杯——修改数组（并查集）

**

思路

**常规思路用哈希表的思想，设置bool数组标识是否被占用过，但是发生矛盾时将会造成查找需要遍历整个数组，比如，1，2，3……100000已连续占用，此时再插入1，将会一直遍历这100000个数，极端情况下，插入100000个1，将是n平方的复杂度。 如何快速查找到插入位置，这就引入了并查集，引入数组mp表示本位置插入元素后，下一个等值元素应该插入的位置，这样寻找插入位置将由原来的O（n）变为O（1）。（当然，维护并查集也要消耗时间） 下面是详细代码：

并查集就一个findMp（）函数，这里采用了根节点指向0的写法，更好初始化。

#include <bits/stdc++.h>
using namespace std;
const int maxn=100001;
int mp[maxn];
int findMp(int x)
{
          
   
    int source=x;
    while(mp[x])
    {
          
   
        x=mp[x];
    }
    int res=x;
    x=source;
    while(mp[x])
    {
          
   
        int temp=mp[x];
        mp[x]=res;
        x=temp;
    }
    return res;
}
int main()
{
          
   
    memset(mp,0,sizeof mp);
    vector<int> res;
    int n;
    cin>>n;
    int temp;
    for(int i=1;i<=n;i++)
    {
          
   
        cin>>temp;
        int index=findMp(temp);
        mp[index]=index+1;
        res.push_back(index);
    }
    for(vector<int>::iterator it=res.begin();it!=res.end();it++)
    {
          
   
        cout<<*it<<" ";
    }
}