思路:

题目的主要信息:
题目需要对一个长为n的序列p进行排序,但是排序不是简单的进行,只能通过交换第x和第y的值。需要我们求解最小的序列。
需要注意的地方:

  • 交换序列对中的值为p中元素的下标,而非p中元素的值

方法一:并查集

首先我们考虑,有m对可以交换,其中可能会出现(a,b) (b,c)这种情况,即a能与b交换,b能与c交换,变相等于a能与c交换,[a,b,c]这三个元素可以互通,如果我们能把所有互通的元素集合都按照从小到大的顺序排序,那么最后得到的序列就是最小序列。
这个思想就是并查集,通过不断的合并查找找到互通的集合。首先我们先对序列中的每个节点的根节点初始化为它本身,通过对可交换序列的合并,我们就得到了一个个内部互通的集合vec[i],对这个集合按照值的大小进行排序,而后重新放到对应的标号中。具体过程如下图所示:

图片说明

具体做法:

class Solution {
public:
    /**
     * 返回牛牛所能得到的字典序最小的排列
     * @param n int整型 
     * @param m int整型 
     * @param perm int整型vector 
     * @param Pair Point类vector 
     * @return int整型vector
     */
    int father[100010];
    int a[100010];
    vector<int> vec[100010];
    int find(int root) //寻找根节点
    { 
        if(father[root] == root)//如果root的父节点就为自己本身则直接返回自身
        {
            return root; 
        }
        else//否则,递归寻找root的根节点
        {
            father[root] = find(father[root]);
            return father[root];
        }
    }
    void Union(int x, int y) //合并x和y的根节点
    {
        father[find(x)] = find(y); 
    }
    vector<int> solve(int n, int m, vector<int>& perm, vector<Point>& Pair) {
        for (int i = 1;i <= n; i++) 
        {
            a[i] = perm[i-1];
            father[i] = i;//初始化每个节点的父节点
        }
        for (int i = 0;i < m;i++) 
        {
            Union(Pair[i].x, Pair[i].y);//合并可以交换的顶点,他们可以在一个集合中排序
        }
        for (int i = 1; i <= n; i++)
        {
            vec[find(i)].push_back(i);//保存每个单独的集合的序列号
        }
        for (int i = 1; i <= n; i++) {
            vector<int> temp;
            for (auto j: vec[i]) 
            {
                temp.push_back(a[j]);//temp中保存每个单独集合的值
            }
            sort(temp.begin(), temp.end());//对每个集合进行排序
            for(int j=0;j < vec[i].size(); j++)
            {
                a[vec[i][j]] = temp[j];//将每个排序后的集合按照顺序放入a数组中
            }
        }
        vector<int> ans;
        for (int i = 1; i <= n; i++) 
        {
            ans.push_back(a[i]);//将a数组转化为向量返回
        }
        return ans;
    }
};

复杂度分析:

  • 时间复杂度:图片说明 ,最坏情况下,合并操作时间复杂度为图片说明 ,总共需要进行m次合并。对于每一个根需要遍历他的连通度。
  • 空间复杂度:图片说明 ,序列p最多有n个节点。

方法二:优化并查集

并查集还可再进行优化。在对可交换对合并的时候,方法一默认合并方法是默认的,没有考虑两个集合的大小。根据霍夫曼树的思想,为了减少find函数遍历时候的开销,我们让规模更加庞大的树更靠近根节点,所以在合并的时候,我们对两个集合的规模count[r1]、count[r2]进行判断,如果count[r1]<count[r2],则将r1根节点改为r2,并且更新r2节点的树规模大小count[r2]=count[r2]+count[r1]。
具体做法:

class Solution {
public:
    /**
     * 返回牛牛所能得到的字典序最小的排列
     * @param n int整型 
     * @param m int整型 
     * @param perm int整型vector 
     * @param Pair Point类vector 
     * @return int整型vector
     */
    int father[100010];
    int a[100010];
    vector<int> vec[100010];
    int count[100010];//统计每个子树的规模大小
    int find(int root) //寻找根节点
    { 
        if(father[root] == root)//如果root的父节点就为自己本身则直接返回自身
        {
            return root; 
        }
        else//否则,递归寻找root的根节点
        {
            father[root] = find(father[root]);
            return father[root];
        }
    }
    void Union(int x, int y) //合并x和y的根节点
    {
        int r1,r2;
        r1 = find(x);
        r2 = find(y);
        if(r1!=r2)
        {
            if(count[r1]<count[r2])//判断两个集合的大小,向规模大的集合靠拢
            {
                father[find(x)] = find(y); 
                count[r2]+=count[r1];//更新根节点的规模大小
            }
            else{
                father[find(y)] = find(x); 
                count[r1]+=count[r2];
            }
        }
    }
    vector<int> solve(int n, int m, vector<int>& perm, vector<Point>& Pair) {
        for (int i = 1;i <= n; i++) 
        {
            a[i] = perm[i-1];
            father[i] = i;//初始化每个节点的父节点
            count[i] = 1;//初始化集合大小
        }
        for (int i = 0;i < m;i++) 
        {
            Union(Pair[i].x, Pair[i].y);//合并可以交换的顶点,他们可以在一个集合中排序
        }
        for (int i = 1; i <= n; i++)
        {
            vec[find(i)].push_back(i);//保存每个单独的集合的序列号
        }
        for (int i = 1; i <= n; i++) {
            vector<int> temp;
            for (auto j: vec[i]) 
            {
                temp.push_back(a[j]);//temp中保存每个单独集合的值
            }
            sort(temp.begin(), temp.end());//对每个集合进行排序
            for(int j=0;j < vec[i].size(); j++)
            {
                a[vec[i][j]] = temp[j];//将每个排序后的集合按照顺序放入a数组中
            }
        }
        vector<int> ans;
        for (int i = 1; i <= n; i++) 
        {
            ans.push_back(a[i]);//将a数组转化为向量返回
        }
        return ans;
    }
};

复杂度分析:

  • 时间复杂度:图片说明 ,最坏情况下,合并操作时间复杂度为图片说明 ,总共需要进行m次合并。对于每一个根需要遍历他的连通度。
  • 空间复杂度:图片说明 ,序列p最多有n个节点。