题解 | #旋转跳跃#

思路：

题目的主要信息：
题目需要对一个长为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个节点。