题解 | #旋转跳跃#

题意整理

• 给定一个长度为n的排列p，以及m个数对，每个数对包含一个和一个。
• 可以将排列p中下标对应值和下标对应值互换，数对的使用顺序和次数不限。
• 求任意次操作后字典序最小的排列p。

方法一（并查集）

1.解题思路

并查集简述：

并查集主要用于解决图中的连通域问题，起初并查集里包含n个节点，每个节点都有一个根，初始情况下，根指向自身。然后有两个关键方法，一个是find，一个是union。find用于查找当前节点的根，union用于连接两个节点，连接以后处于同一个连通域，即共享一个根。

• 首先新建并查集，遍历Pair数组，连接对应节点。
• 再新建两个邻接表，一个用于记录当前根对应连通域所有节点的下标，另一个用于记录当前根对应连通域所有节点的值。
• 遍历所有可能的根，然后对连通域内的节点值排序，赋值到perm数组。直到遍历完所有的根。

动图展示：

2.代码实现

import java.util.*;

/*
 * public class Point {
 *   int x;
 *   int y;
 * }
 */

public class Solution {
    /**
     * 返回牛牛所能得到的字典序最小的排列
     * @param n int整型 
     * @param m int整型 
     * @param perm int整型一维数组 
     * @param Pair Point类一维数组 
     * @return int整型一维数组
     */
    public int[] solve (int n, int m, int[] perm, Point[] Pair) {
        //新建并查集
        UF uf=new UF(n);
        //连接对应节点
        for(Point point:Pair){
            uf.union(point.x-1,point.y-1);
        }

        //初始化邻接表，分别记录可交换节点的Id和Value
        List<List<Integer>> IdGraph=new ArrayList<>();
        List<List<Integer>> ValueGraph=new ArrayList<>();

        for(int i=0;i<n;i++){
            IdGraph.add(new ArrayList<>());
            ValueGraph.add(new ArrayList<>());
        }

        for(int i=0;i<n;i++){
            IdGraph.get(uf.find(i)).add(i);
            ValueGraph.get(uf.find(i)).add(perm[i]);
        }

        for(int i=0;i<n;i++){
            //找到可交换的所有节点，将其Value进行排序
            Collections.sort(ValueGraph.get(i));
            for(int j=0;j<IdGraph.get(i).size();j++){
                //将排序后的节点写入perm排列，保证还是那些Value对应的Id
                perm[IdGraph.get(i).get(j)]=ValueGraph.get(i).get(j);
            }
        }
        return perm;
    }

}

//并查集结构
class UF{
    //父数组
    int[] parent;

    UF(int n){
        //初始化
        parent=new int[n];
        for(int i=0;i<n;i++){
            parent[i]=i;
        }
    }

    //连接p节点和q节点
    public void union(int p,int q){
        //首先找打对应根节点，然后将其中一个节点的父置为另一个节点
        int pRoot=find(p);
        int qRoot=find(q);
        if(pRoot==qRoot) return;
        parent[pRoot]=qRoot;

    }

    //寻找根节点
    public int find(int x){
        //如果根节点不是自身，则将其父节点置为父节点的父节点
        while(x!=parent[x]){
            parent[x]=parent[parent[x]];
            //继续沿父节点往上找
            x=parent[x];
        }
        return x;
    }
}

3.复杂度分析

• 时间复杂度：最坏情况下，并查集union操作的时间复杂度为，需要进行m次，于是所有union操作的时间复杂度是，然后假设并查集最后有k个根，每个根连通域大小为，则时间复杂度为 ,所以最终的时间复杂度为 。
• 空间复杂度：所有连通域的总节点个数最多为n，所以空间复杂度为。

方法二（按秩合并）

1.解题思路

基本思路和方法一相同。对并查集的union操作进行了优化。原来的union方式会导致某些节点离根越来越远，从而find方法耗时越来越长。假设现在有两个连通域，一个连通域根是pRoot，大小是m，另一个连通域根是qRoot，大小是n，并且m<n。如果连接pRoot和qRoot,将pRoot作为新连通域的根，则会有n个节点的查找路径长度加一，如果将qRoot作为新连通域的根，则会有m个节点的查找路径长度加一，显然让qRoot作为新的根，对find效率的影响会更小一点。

2.代码实现

import java.util.*;

/*
 * public class Point {
 *   int x;
 *   int y;
 * }
 */

public class Solution {
    /**
     * 返回牛牛所能得到的字典序最小的排列
     * @param n int整型 
     * @param m int整型 
     * @param perm int整型一维数组 
     * @param Pair Point类一维数组 
     * @return int整型一维数组
     */
    public int[] solve (int n, int m, int[] perm, Point[] Pair) {
        //新建并查集
        UF uf=new UF(n);
        //连接对应节点
        for(Point point:Pair){
            uf.union(point.x-1,point.y-1);
        }

        //初始化邻接表，分别记录可交换节点的Id和Value
        List<List<Integer>> IdGraph=new ArrayList<>();
        List<List<Integer>> ValueGraph=new ArrayList<>();

        for(int i=0;i<n;i++){
            IdGraph.add(new ArrayList<>());
            ValueGraph.add(new ArrayList<>());
        }

        for(int i=0;i<n;i++){
            IdGraph.get(uf.find(i)).add(i);
            ValueGraph.get(uf.find(i)).add(perm[i]);
        }

        for(int i=0;i<n;i++){
            //找到可交换的所有节点，将其Value进行排序
            Collections.sort(ValueGraph.get(i));
            for(int j=0;j<IdGraph.get(i).size();j++){
                //将排序后的节点写入perm排列，保证还是那些Value对应的Id
                perm[IdGraph.get(i).get(j)]=ValueGraph.get(i).get(j);
            }
        }
        return perm;
    }

}

//并查集结构
class UF{
    //父数组
    int[] parent;
    //秩数组
    int[] size;

    UF(int n){
        //初始化
        parent=new int[n];
        size=new int[n];
        for(int i=0;i<n;i++){
            parent[i]=i;
            size[i]=1;
        }
    }

    //连接p节点和q节点
    public void union(int p,int q){
        //首先找打对应根节点，然后将其中一个节点的父置为另一个节点
        int pRoot=find(p);
        int qRoot=find(q);
        if(pRoot==qRoot) return;
        //将秩较小的根指向秩较大的根
        if(size[pRoot]<size[qRoot]){
            parent[pRoot]=qRoot;
        }
        else{
            parent[qRoot]=pRoot;
        }

    }

    //寻找根节点
    public int find(int x){
        //如果根节点不是自身，则将其父节点置为父节点的父节点
        while(x!=parent[x]){
            parent[x]=parent[parent[x]];
            //继续沿父节点往上找
            x=parent[x];
        }
        return x;
    }
}

3.复杂度分析

• 时间复杂度：最坏情况下，并查集union操作的时间复杂度为，需要进行m次，于是所有union操作的时间复杂度是，然后假设并查集最后有k个根，每个根连通域大小为，则时间复杂度为 ,所以最终的时间复杂度为 。
• 空间复杂度：所有连通域的总节点个数最多为n，所以空间复杂度为。